53. Maximum Subarray

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`.

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.

Thoughts:

1. Divide and Conquer: For each subarray, calculate four values:
1. m (largest sum of this subarray),
2. l (largest sum starting from the left most element),
3. r (largest sum ending with the rightmost element),
4. s (the sum of the whole subarray).
2. Greedy: find the largest difference between the sums summing from left to right. The largest difference corresponds to the sub-array with largest sum.
3. DP: dp[i] : max sum till i.
1. dp[i] = max(dp[i-1], nums[i] + dp[i-1])
2. have a variable to record max dp[i] so far

Code (DP) Time Complexity O(n), Space Complexity O(n)

``````class Solution {
public:
int maxSubArray(vector<int>& nums) {
int n = nums.size();
if( n == 0 ) return 0;
if(n == 1) return nums[0];
int sum = nums[0];
int dp [n];  fill_n(dp, n, 0); dp[0] = nums[0];
for ( int i = 1; i < n; i++){
dp[i] = dp[i-1] > 0 ? dp[i-1] + nums[i]: nums[i];
if(dp[i] > sum) sum = dp[i];
}

return sum;
}
};
``````

Code (Divide and Conquer) Time Complexity O(nlogn), Space Complexity O(nlogn)

``````struct val {
int l, m, r, s;
//m (largest sum of this subarray),
//l (largest sum starting from the left most element),
//r (largest sum ending with the rightmost element),
//s (the sum of the whole subarray).

val(int l, int m, int r, int s):l(l), m(m), r(r), s(s){}
};

class Solution {
public:
val dac(int A[], int n) {
if(n == 1) return val(A[0], A[0], A[0], A[0]);
val v1 = dac(A, n / 2), v2 = dac(A + n / 2, n - n / 2);
int l, m, r, s;
l = max(v1.l, v1.s + v2.l);
m = max(v1.r + v2.l, max(v1.m, v2.m));
r = max(v2.r, v1.r + v2.s);
s = v1.s + v2.s;
return val(l, m, r, s);
}
int maxSubArray(int A[], int n) {
val v = dac(A, n);
return v.m;
}
};
``````

Code (Greedy) Time Complexity: O(n), Space Complexity: O(1)

``````class Solution {
public:
int maxSubArray(int A[], int n) {
int sum = 0, min = 0, res = A[0];
for(int i = 0; i < n; i++) {
sum += A[i];
if(sum - min > res) res = sum - min;
if(sum < min) min = sum;
}
return res;
}
};
``````