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

---

The O(n) solution is referred from Kadane's Algorithm. Its basic idea is that the maximum sum of subarray ending at A[i] is the max of maximum sum of subarray ending at A[i-1] plus A[i] and A[i]. For the idea of divide and conquer, the problem can be divided into 3 cases: 1. the sum may occur in the left side of the array; 2. It may occur in the right side of the array; 3. It may occur across the middle point of the array. I implemented the first method in C++, and second one in Python.

C++ Code:

/*
 * func: max_subarray
 * goal: find the contiuous subarray whose sum is the largest
 * @param A: input array
 * @param n: array size n
 * @return: maximum sum
 */
/*
 * Iterate from the start, and find the possible starting position
 * until to the end to find the meximum
 * complexity: time O(n), space O(1)
 */
int max_subarray(int A[], int n){
    assert(n > 0);
    int result = A[0], sum = 0;
    for(int i=0; i<n; ++i){
        //If A[i] is larger than current sum
        //Then A[i] could be an available starting point
        sum = std::max(sum + A[i], A[i]);
        result = std::max(result, sum);
    }
    return result;
}

Python Code:

# func: find the maximum sum of contiguous subarray that crosses the mid point
# @param A: input list A
# @return: maximum sum
def max_crossing_sum(A):
    left_sum = -2147483648
    sum = 0
    i = (len(A)-1)/2
    print i
    #Get the maximum sum of the left part
    while i >= 0:
        sum += A[i]
        if sum > left_sum:
            left_sum = sum
        i -= 1
    #Get the maximum sum of the right part
    i = (len(A)-1)/2+1
    print i
    right_sum = -2147483648
    sum = 0
    while i < len(A):
        sum += A[i]
        if sum > right_sum:
            right_sum = sum
        i += 1
    print left_sum + right_sum
    return left_sum + right_sum

# func: find the contiguous subarray whose sum is maximal
# @param A: a list of integers
# @return: the maximal sum
# complexity: time O(nlogn)
def max_subarray(A):
    if A:
        left = 0
        right = len(A)-1
        if left >= right:
            return A[left]

        mid = left + (right-left) / 2
        #The maximum contiguous subarray sum is either from left side, right side or cross left side and right side
        return max(max_subarray(A[left:mid+1]), max_subarray(A[mid+1:right+1]), max_crossing_sum(A[left:right+1]))

Reference Link:

1. Maximum subarray problem: http://en.wikipedia.org/wiki/Kadane%27s_Algorithm

2. [closed] Maximum Subarray - LeetCode: http://discuss.leetcode.com/questions/231/maximum-subarray

3. Divide and Conquer | Set 3 (Maximum Subarray Sum) | GeeksforGeeks: http://www.geeksforgeeks.org/divide-and-conquer-maximum-sum-subarray/