Leetcode 53: Maximum Subarray

https://leetcode.com/problems/maximum-subarray/

import sys
class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
            
        max_sum = -sys.maxint
        tmp_sum = 0
        
        for i in xrange(0, len(nums)):
            if tmp_sum + nums[i] >= 0:
                tmp_sum += nums[i]
                max_sum = max(max_sum, tmp_sum)
            else:
                tmp_sum = 0
                # for corner case where the array only contains negative nums
                max_sum = max(max_sum, nums[i])
                
        return max_sum

 

Idea

We create a variable `tmp_sum` to record what is the maximum sum you have seen. If you visit a positive number, you can definitely add it to `tmp_sum`; if you visit a negative number, as long as `tmp_sum` is still larger than 0, you can add it also. If a negative number makes `tmp_sum` to negative, that means the maximum sum cannot happen by including this negative number and any arbitrary numbers before it.

 

Another idea is to use divide and conquer:

https://leetcode.com/discuss/694/how-solve-maximum-subarray-using-divide-and-conquer-approach

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.

Here is a sample code for divide and conquer solution. Please try to understand the algorithm before look at the code:

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);
    }
    
    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];
        int temp = 0;
        for(int i=middle;i>=left;i--) {
            temp += A[i];
            if(temp > leftmax) leftmax = temp;
        }
        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);
    }
};

 

The divide and conquer algorithm takes O(nlogn) time and O(n) space just as merge sort.