 wayetan
12/27/2013 - 9:17 AM

## Maximum Subarray

Maximum Subarray

``````/**
* More practice:
* If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.
*/
public class Solution {
public int maxSubArray(int[] A) {
if (A.length == 0)
return 0;
return maxSubArray(A, 0, A.length - 1);
}

public int maxSubArray(int[] A, int low, int high) {
int leftMidSum = Integer.MIN_VALUE, rightMidSum = Integer.MIN_VALUE, sum = 0;
if (low == high)
return A[low];
int mid = low + (high - low) / 2;
int maxLeftSum = maxSubArray(A, low, mid);
int maxRightSum = maxSubArray(A, mid + 1, high);
// across sum
for (int i = mid; i >= low; i--) {
sum += A[i];
leftMidSum = (sum > leftMidSum) ? sum : leftMidSum;
}
// reset sum as 0
sum = 0;
for (int i = mid + 1; i <= high; i++) {
sum += A[i];
rightMidSum = (sum > rightMidSum) ? sum : rightMidSum;
}
return max3(maxLeftSum, maxRightSum, (leftMidSum + rightMidSum));
}

public int max3(int a, int b, int c) {
return a > b ? (a > c ? a : c) : (b > c ? b : c);
}
}``````
``````/**
* Find the contiguous subarray within an array (containing at least one number) which has the largest sum.
* For example, given the array [−2,1,−3,4,−1,2,1,−5,4],
* the contiguous subarray [4,−1,2,1] has the largest sum = 6.
*/
public class Solution {
public int maxSubArray(int[] A) {
int res = A, sum = 0;
for(int i = 0; i < A.length; ++i){
sum = Math.max(sum + A[i], A[i]);
res = Math.max(res, sum);
}
return res;
}
}``````