Problem

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.

Solution:

Time O(n), space O(1)

Use two variables "Res" and "preSum"

1. res to store the return result up to date
2. preSum to store the best up to date prefix sum result

be careful:

1. 如果 preSum at i < nums[i], then let preSum = nums[i]. Start from fresh because all previous prefix sum doesn't matter
2. Don't need an array to store all the prefix sum from all the way to index 0.
3. 2 variables. One to store the best up to date result, one to store prefix sum, because even though preSum may take a hit from current nums[i], it may still rebounce to even larger at some nums[i+k]

Python:

def maxSubArray(self, nums):

    preSum = nums[0]
    res = nums[0]

    for i in range(1, len(nums)):
        preSum = max(preSum + nums[i], nums[i])
        res = max(preSum, res)

    return res

Divide and Conquer Approach:

Time O( n log n ) for divide and conquer approach. Space O(1)

Step1. Select the middle element of the array.
So the maximum subarray may contain that middle element or not.

Step 2.1 If the maximum subarray does not contain the middle element, then we can apply the same algorithm to the the subarray to the left of the middle element and the subarray to the right of the middle element.

Step 2.2 If the maximum subarray does contain the middle element, then the result will be simply the maximum suffix subarray of the left subarray plus the maximum prefix subarray of the right subarray

Step 3 return the maximum of those three answer.

class Solution {
    public int maxSubArray(int A[], int n) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
        if(n==0) return 0;
        return maxSubArrayHelperFunction(A,0,n-1);
    }

    public int maxSubArrayHelperFunction(int A[], int left, int right) {
        if(right == left) return A[left];
        int middle = (left+right)/2;
        int leftans = maxSubArrayHelperFunction(A, left, middle);
        int rightans = maxSubArrayHelperFunction(A, middle+1, right);
        int leftmax = A[middle];
        int rightmax = A[middle+1];
        // here assumes mid is part of the max subarray to the left
        int temp = 0;
        for(int i=middle;i>=left;i--) {
            temp += A[i];
            if(temp > leftmax) leftmax = temp;
        }
        // here assumes mid+1 is part of the max subarray to the right
        temp = 0;
        for(int i=middle+1;i<=right;i++) {
            temp += A[i];
            if(temp > rightmax) rightmax = temp;
        }
        return max(max(leftans, rightans),leftmax+rightmax);
    }
};

ref: https://discuss.leetcode.com/topic/426/how-to-solve-maximum-subarray-by-using-the-divide-and-conquer-approach