Lintcode: Maximum Subarray II
5473 단어 array
Given an array of integers, find two non-overlapping subarrays which have the largest sum.
The number in each subarray should be contiguous.
Return the largest sum.
Note
The subarray should contain at least one number
Example
For given [1, 3, -1, 2, -1, 2], the two subarrays are [1, 3] and [2, -1, 2] or [1, 3, -1, 2] and [2], they both have the largest sum 7.
Challenge
Can you do it in time complexity O(n) ?사고방식: 수조를 두 부분으로 나누면 i와 i+1(0<=i
1 public class Solution {
2 /**
3 * @param nums: A list of integers
4 * @return: An integer denotes the sum of max two non-overlapping subarrays
5 */
6 public int maxTwoSubArrays(ArrayList<Integer> nums) {
7 // write your code
8 if (nums==null || nums.size()==0) return 0;
9 int len = nums.size();
10 int lLocal = nums.get(0);
11 int[] lGlobal = new int[len];
12 lGlobal[0] = lLocal;
13 for (int i=1; i<len; i++) {
14 lLocal = Math.max(lLocal+nums.get(i), nums.get(i));
15 lGlobal[i] = Math.max(lLocal, lGlobal[i-1]);
16 }
17
18 int rLocal = nums.get(len-1);
19 int[] rGlobal = new int[len];
20 rGlobal[len-1] = rLocal;
21 for (int i=len-2; i>=0; i--) {
22 rLocal = Math.max(rLocal+nums.get(i), nums.get(i));
23 rGlobal[i] = Math.max(rLocal, rGlobal[i+1]);
24 }
25
26 int res = Integer.MIN_VALUE;
27 for (int k=0; k<len-1; k++) {
28 if (res < lGlobal[k]+rGlobal[k+1])
29 res = lGlobal[k] + rGlobal[k+1];
30 }
31 return res;
32 }
33 } 이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
CloudFirestore의 array를 사용해보기CloudFirestore의 array를 사용하고 있는 기사가 별로 발견되지 않았으므로, 비망록적으로 남겨 둔다. 기재할 것 CloudFirestore 필드의 배열 유형 사용 (이번에는 추가) 기재하지 않는 것 Fi...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
