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

Difficulty Medium

Related Problems [LeetCode 152] Maxmimum Product Subarray

Analysis

Idea 1

One dimentional dp. Use a variable dpSum to record historical max sum (dpSum = max(dpSum, curSum)) before index i, use another variable curSum to record the current sum at index i. if curSum < 0, we should drop the sum make up of visited element, reset sum = 0. and keep finding a larger one.

Idea 2

Use divide and conquer approach. Assume that there is a section in given array that elements in that section have a max sum. If we take mid = (left + right) / 2, there will be three situations:

• 1. the max sum is in the left part, which is nums[left, mid - 1]
• 1. the max sum is in the right part, which is nums[mid + 1, right]
• 1. the max sum crosses the mid element, by which means that we need to take the max sum in section [left, mid - 1], and max sum in [mid + 1, right], plus mid element's value, we get the resulting sum.

So, we apply recursion algorithms on situation 1 & 2, and then compare the result to situation 3, we can get the answer.

Divide

Eventually will divide an array to a single element, and execute algorithm on it (e.g. get max sum from it in this problem), when reduce down to only one element, we essentially return it (becasue max sum is itself)

Conquer

When we reduce down to only one element, we will be return up, and climbing up the stack one level at a time.

e.g. climb up at top, we return the max sum of current element and the returned sum from previous level ... climb up at bottom + 2, we return the max sum of current element and the returned sum from previous level climb up at bottom + 1, we return the max sum of current element and the returned sum from previous level climb up at bottom, we return the only element as the max sum.

Solutions

1. Cpp solution 9ms

class Solution{
public:
    int maxSubArray(vector<int>& nums){
        int curSum = 0;      // local sum
        int dpSum = nums[0]; // global max sum

        for (unsigned int i = 0; i < nums.size(); ++i){
            curSum += nums[i];
            dpSum = max(dpSum, curSum);      // update global max sum in each iteration
            if(curSum < 0) {
                curSum = 0;
            }
        }
        return dpSum;
    }
};

2. Cpp solution `9ms`

```cpp
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int n = nums.size();

        int endhere = nums[0];
        int maxsum = nums[0];
        for(int i = 1; i < n; ++i){
            endhere = max(endhere + nums[i], nums[i]);
            maxsum = max(endhere, maxsum);
        }
        return maxsum;
    }
};

1. Cpp solution 15ms

class Solution {
public:
    int maxSubArray(vector<int> & A) {
        int n = A.size();
        return divide(A, 0, n - 1, INT_MIN);
    }

    int divide(int A[], int left, int right, int tmax) {
        if(left > right) {
            return INT_MIN;
        }

        int mid = left + (right - left) / 2;
        int lmax = divide(A, left, mid - 1, tmax);
        int rmax = divide(A, mid + 1, right, tmax);

        tmax = max(tmax, lmax);
        tmax = max(tmax, rmax);

        int sum = 0;
        int mlmax = 0;

        // Get max sum from [left, mid - 1]
        for(int i = mid - 1; i >= left; i--) {
            sum += A[i];
            mlmax = max(mlmax, sum);
        }

        sum = 0;
        int mrmax = 0;

        // Get max sum from [mid + 1, right]
        for(int i = mid + 1; i <= right; i++) {
            sum += A[i];
            mrmax = max(mrmax, sum);
        }

        tmax = max(tmax, A[mid] + mlmax + mrmax);
        return tmax;
    }
};

1. Recursive

int maxSubArray(int[] array, int low, int high){
    if (low > high)
       return 0;
    if (low == high)
       return max(0, array[low]);

    int middle = (low + high) / 2;
        int leftMax = 0, sum = 0;
    for (i = middle; i ≥ low; i--) {
       sum += array[i];
       if (sum > leftMax)
           leftMax = sum;
    }

    sum = 0;
    int rightMax = 0;
    for (i = middle+1; i ≤ high; i++) {
       sum += array[i];
       if (sum > rightMax)
           rightMax = sum;
    }

    return max(leftMax + rightMax, max(maxSubArray(nums, low, mid), maxSubArray(mid+1, high)));
 }

1. Go (DP)13ms

func maxSubArray(nums []int) int {
    curSum, dpSum := 0, nums[0]

    for i := 0; i < len(nums); i++ {
        curSum += nums[i]
        dpSum = max(dpSum, curSum)
        if curSum < 0 {
            curSum = 0
        }
    }

    return dpSum
}

func max(a, b int) int {
    return int(math.Max(float64(a), float64(b)))
}

1. Go (divide and conquer) 13ms

func maxSubArray(nums []int) int {


    return dpSum
}

func max(a, b int) int {
    return int(math.Max(float64(a), float64(b)))
}

Reference