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.

click to show more practice.

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;
    }
};