Find the contiguous subarray within an array (containing at least one number) which has the largest sum.
For example, given the array
the contiguous subarray
[-2,1,-3,4,-1,2,1,-5,4],the contiguous subarray
[4,-1,2,1] has the largest sum = 6.
this problem was discussed by Jon Bentley (Sep. 1984 Vol. 27 No. 9 Communications of the ACM P885)
the paragraph below was copied from his paper (with a little modifications)
algorithm that operates on arrays: it starts at the left end (element A[1]) and scans through to the right end (element A[n]), keeping track of the maximum sum subvector seen so far. The maximum is initially A[0]. Suppose we've solved the problem for A[1 .. i - 1]; how can we extend that to A[1 .. i]? The maximum
sum in the first I elements is either the maximum sum in the first i - 1 elements (which we'll call MaxSoFar), or it is that of a subvector that ends in position i (which we'll call MaxEndingHere).
sum in the first I elements is either the maximum sum in the first i - 1 elements (which we'll call MaxSoFar), or it is that of a subvector that ends in position i (which we'll call MaxEndingHere).
MaxEndingHere is either A[i] plus the previous MaxEndingHere, or just A[i], whichever is larger.
public static int maxSubArray(int[] A) {
int maxSoFar=A[0], maxEndingHere=A[0];
for (int i=1;i<A.length;++i){
maxEndingHere= Math.max(maxEndingHere+A[i],A[i]);
maxSoFar=Math.max(maxSoFar, maxEndingHere);
}
return maxSoFar;
}
From http://en.wikipedia.org/wiki/Maximum_subarray_problem
Kadane's algorithm consists of a scan through the array values, computing at each position the maximum (positive sum) subarray ending at that position. This subarray is either empty (in which case its sum is zero) or consists of one more element than the maximum subarray ending at the previous position.
http://www.geeksforgeeks.org/divide-and-conquer-maximum-sum-subarray/
1) Divide the given array in two halves
2) Return the maximum of following three
….a) Maximum subarray sum in left half (Make a recursive call)
….b) Maximum subarray sum in right half (Make a recursive call)
….c) Maximum subarray sum such that the subarray crosses
We can easily find the crossing sum in linear time. The idea is simple, find the maximum sum starting from mid point and ending at some point on left of mid, then find the maximum sum starting from mid + 1 and ending with sum point on right of mid + 1. Finally, combine the two and return.
X. dp
https://discuss.leetcode.com/topic/6413/dp-solution-some-thoughts
Kedan Algorithm
http://www.geeksforgeeks.org/largest-sum-contiguous-subarray/
The implementation handles the case when all numbers in array are negative.
http://algorithms.tutorialhorizon.com/dynamic-programming-maximum-subarray-problem/
To calculate the solution for any element at index “i” has two options
int [] solution = new int[a.length+1];
solution[0] = 0;
for (int j = 1; j <solution.length ; j++) {
solution[j] = Math.max(solution[j-1]+a[j-1],0);
}
//now return the maximum in the solution array
int result = solution[0];
for (int j = 1; j <solution.length ; j++) {
if(result<solution[j])
result = solution[j];
}
return result;
}
Kadane's algorithm consists of a scan through the array values, computing at each position the maximum (positive sum) subarray ending at that position. This subarray is either empty (in which case its sum is zero) or consists of one more element than the maximum subarray ending at the previous position.
public int maxSubArray(int[] A) { int max = A[0]; int[] sum = new int[A.length]; sum[0] = A[0]; for (int i = 1; i < A.length; i++) { sum[i] = Math.max(A[i], sum[i - 1] + A[i]); max = Math.max(max, sum[i]); } return max; } |
Above program can be optimized further, if we compare max_so_far with max_ending_here only if max_ending_here is greater than 0. The implementation handles the case when all numbers in array are negative. From http://www.geeksforgeeks.org/largest-sum-contiguous-subarray/
int maxSubArraySum(int a[], int size){ int max_so_far = a[0], i; int curr_max = a[0]; for (i = 1; i < size; i++) { curr_max = max(a[i], curr_max+a[i]); max_so_far = max(max_so_far, curr_max); } return max_so_far;}
Also refer to http://en.wikipedia.org/wiki/Maximum_subarray_problem
http://www.geeksforgeeks.org/largest-sum-contiguous-subarray/
X. Divide and Conquer
https://discuss.leetcode.com/topic/42213/my-divide-and-conquer-solution-in-java-under-instruction-of-clrs-o-nlogn
http://www.geeksforgeeks.org/largest-sum-contiguous-subarray/
X. Divide and Conquer
https://discuss.leetcode.com/topic/42213/my-divide-and-conquer-solution-in-java-under-instruction-of-clrs-o-nlogn
public int maxSubArray(int[] nums) {
return Subarray(nums, 0 ,nums.length -1 );
}
public int Subarray(int[] A,int left, int right){
if(left == right){return A[left];}
int mid = left + (right - left) / 2;
int leftSum = Subarray(A,left,mid);// left part
int rightSum = Subarray(A,mid+1,right);//right part
int crossSum = crossSubarray(A,left,right);// cross part
if(leftSum >= rightSum && leftSum >= crossSum){// left part is max
return leftSum;
}
if(rightSum >= leftSum && rightSum >= crossSum){// right part is max
return rightSum;
}
return crossSum; // cross part is max
}
public int crossSubarray(int[] A,int left,int right){
int leftSum = Integer.MIN_VALUE;
int rightSum = Integer.MIN_VALUE;
int sum = 0;
int mid = left + (right - left) / 2;
for(int i = mid; i >= left ; i--){
sum = sum + A[i];
if(leftSum < sum){
leftSum = sum;
}
}
sum = 0;
for(int j = mid + 1; j <= right; j++){
sum = sum + A[j];
if(rightSum < sum){
rightSum = sum;
}
}
return leftSum + rightSum;
}http://www.geeksforgeeks.org/divide-and-conquer-maximum-sum-subarray/
1) Divide the given array in two halves
2) Return the maximum of following three
….a) Maximum subarray sum in left half (Make a recursive call)
….b) Maximum subarray sum in right half (Make a recursive call)
….c) Maximum subarray sum such that the subarray crosses
We can easily find the crossing sum in linear time. The idea is simple, find the maximum sum starting from mid point and ending at some point on left of mid, then find the maximum sum starting from mid + 1 and ending with sum point on right of mid + 1. Finally, combine the two and return.
int maxCrossingSum(int arr[], int l, int m, int h){ // Include elements on left of mid. int sum = 0; int left_sum = INT_MIN; for (int i = m; i >= l; i--) { sum = sum + arr[i]; if (sum > left_sum) left_sum = sum; } // Include elements on right of mid sum = 0; int right_sum = INT_MIN; for (int i = m+1; i <= h; i++) { sum = sum + arr[i]; if (sum > right_sum) right_sum = sum; } // Return sum of elements on left and right of mid return left_sum + right_sum;}// Returns sum of maxium sum subarray in aa[l..h]int maxSubArraySum(int arr[], int l, int h){ // Base Case: Only one element if (l == h) return arr[l]; // Find middle point int m = (l + h)/2; /* Return maximum of following three possible cases a) Maximum subarray sum in left half b) Maximum subarray sum in right half c) Maximum subarray sum such that the subarray crosses the midpoint */ return max(maxSubArraySum(arr, l, m), maxSubArraySum(arr, m+1, h), maxCrossingSum(arr, l, m, h));}https://discuss.leetcode.com/topic/6413/dp-solution-some-thoughts
Apparently, this is a optimization problem, which can be usually solved by DP. So when it comes to DP, the first thing for us to figure out is the format of the sub problem(or the state of each sub problem). The format of the sub problem can be helpful when we are trying to come up with the recursive relation.
At first, I think the sub problem should look like:
maxSubArray(int A[], int i, int j), which means the maxSubArray for A[i: j]. In this way, our goal is to figure out what maxSubArray(A, 0, A.length - 1) is. However, if we define the format of the sub problem in this way, it's hard to find the connection from the sub problem to the original problem(at least for me). In other words, I can't find a way to divided the original problem into the sub problems and use the solutions of the sub problems to somehow create the solution of the original one.
So I change the format of the sub problem into something like:
maxSubArray(int A[], int i), which means the maxSubArray for A[0:i ] which must has A[i] as the end element. Note that now the sub problem's format is less flexible and less powerful than the previous one because there's a limitation that A[i] should be contained in that sequence and we have to keep track of each solution of the sub problem to update the global optimal value. However, now the connect between the sub problem & the original one becomes clearer:maxSubArray(A, i) = maxSubArray(A, i - 1) > 0 ? maxSubArray(A, i - 1) : 0 + A[i]; public int maxSubArray(int[] A) {
int n = A.length;
int[] dp = new int[n];//dp[i] means the maximum subarray ending with A[i];
dp[0] = A[0];
int max = dp[0];
for(int i = 1; i < n; i++){
dp[i] = A[i] + (dp[i - 1] > 0 ? dp[i - 1] : 0);
max = Math.max(max, dp[i]);
}
return max;
}
When we are talking about DP, the first problem comes out to our mind should be: what's the statement of the sub-problem, whose format should satisfy that if we've solved a sub-problem, it would be helpful for solving the next-step sub-problem, and, thus, eventually helpful for solving the original problem.
Here is the sub-problem we state: denote
int_local_max[i] as the max-sub-array-sum that ends with nums[i]. The relationship between the two steps is simple: int_local_max[i + 1] = max (int_local_max[i] + nums[i + 1], nums[i + 1]) or int_local_max[i + 1] = (int_local_max[i] > 0) ? int_local_max[i] + nums[i + 1] : nums[i + 1].
Now, all we have to do is to scan through the array, and find which
int_local_max[i] is the maximum of all the int_local_maxs.
To calculate
sum(0,i), you have 2 choices: either adding sum(0,i-1) to a[i], or not. If sum(0,i-1) is negative, adding it to a[i] will only make a smaller sum, so we add only if it's non-negative.sum(0,i) = a[i] + (sum(0,i-1) < 0 ? 0 : sum(0,i-1))
We can then use O(1) space to keep track of the max sum(0, i) so far.
public int maxSubArray(int[] nums) {
if (nums == null || nums.length == 0) { return 0; }
int max = nums[0], sum = nums[0];
for (int i = 1; i < nums.length; i++) {
if (sum < 0) { sum = nums[i]; }
else {sum += nums[i]; }
max = Math.max(max, sum);
}
return max;
}Kedan Algorithm
http://www.geeksforgeeks.org/largest-sum-contiguous-subarray/
The implementation handles the case when all numbers in array are negative.
int maxSubArraySum(int a[], int size){ int max_so_far = a[0], i; int curr_max = a[0]; for (i = 1; i < size; i++) { curr_max = max(a[i], curr_max+a[i]); max_so_far = max(max_so_far, curr_max); } return max_so_far;}int maxSubArraySum(int a[], int size){ int max_so_far = 0, max_ending_here = 0; int i; for(i = 0; i < size; i++) { max_ending_here = max_ending_here + a[i]; if(max_ending_here < 0) max_ending_here = 0; /* Do not compare for all elements. Compare only when max_ending_here > 0 */ else if (max_so_far < max_ending_here) max_so_far = max_ending_here; } return max_so_far;}
“MS(i) is maximum sum ending at index i”
To calculate the solution for any element at index “i” has two options- EITHER added to the solution found till “i-1“th index
- OR start a new sum from the index “i”.
Recursive Solution:
public int solve(int [] a){int [] solution = new int[a.length+1];
solution[0] = 0;
for (int j = 1; j <solution.length ; j++) {
solution[j] = Math.max(solution[j-1]+a[j-1],0);
}
//now return the maximum in the solution array
int result = solution[0];
for (int j = 1; j <solution.length ; j++) {
if(result<solution[j])
result = solution[j];
}
return result;
}
If the array is all negative numbers, what is the correct behavior? Consider this simple array: { - 3, -10,- 5}. You could make a good argument that the maximum sum is either:
1. -3 (if you assume the subsequence can't be empty)
2. 0 (the subsequence has length 0)
3. MINIMUM_INT (essentially, the error case).
We went with option #2 (maxSum = 0), but there's no "correct" answer. This is a great thing to discuss with your interviewer; it will show how detail-oriented you are.
Read full article from LeetCode – Maximum Subarray (Java)