-
Notifications
You must be signed in to change notification settings - Fork 6
Expand file tree
/
Copy pathMaximumSubarrayII.java
More file actions
94 lines (77 loc) · 2.54 KB
/
MaximumSubarrayII.java
File metadata and controls
94 lines (77 loc) · 2.54 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
/*
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) ?
Tags Expand
Greedy Enumeration Array LintCode Copyright SubArray Forward-Backward Traversal
Thinking process:
Find frontSum: largest sum from index 0 till current at each index.
Find endSum: largest sum from end(endSum.length - 1) to current at each index.
Add them up: at any point i, leftSum + rightSum = largest 2 non-overlap sum.
i
i i
i i
i i
*/
public class Solution {
/**
* @param nums: A list of integers
* @return: An integer denotes the sum of max two non-overlapping subarrays
*/
public int maxTwoSubArrays(ArrayList<Integer> nums) {
if (nums == null || nums.size() == 0) {
return 0;
}
int[] frontSum = new int[nums.size()];
int[] endSum = new int[nums.size()];
int maxSum = 0;
frontSum[0] = nums.get(0);
//Init frontSum
for (int i = 1; i < frontSum.length; i++) {
if (frontSum[i - 1] < 0) {
frontSum[i] = nums.get(i);
} else {
frontSum[i] = frontSum[i - 1] + nums.get(i);
}
}
maxSum = frontSum[0];
//Find max
for (int i = 1; i < frontSum.length; i++) {
if (frontSum[i] < maxSum) {
frontSum[i] = maxSum;
} else {
maxSum = frontSum[i];
}
}
//Init endSum
endSum[endSum.length - 1] = nums.get(nums.size() - 1);
for (int i = endSum.length - 2; i >= 0; i--) {
if (endSum[i + 1] < 0) {
endSum[i] = nums.get(i);
} else {
endSum[i] = endSum[i + 1] + nums.get(i);
}
}
//Find max
maxSum = endSum[endSum.length - 1];
for (int i = endSum.length - 2; i >= 0; i--) {
if (endSum[i] < maxSum) {
endSum[i] = maxSum;
} else {
maxSum = endSum[i];
}
}
//Calculate max Sum
maxSum = Integer.MIN_VALUE;
for (int i = 0; i < nums.size() - 1; i++) {
maxSum = Math.max(maxSum, frontSum[i] + endSum[i + 1]);
}
return maxSum;
}
}