Maximum Subarray -- leetcode

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.

算法一

O(n)，在leetcode上实际执行时间为16ms。

class Solution {
public:
    int maxSubArray(int A[], int n) {
        if (n <= 0) return INT_MIN;
        int sum = A[0];
        int maxSum = sum;
        for (int i=1; i<n; i++) {
                sum = max(A[i], sum+A[i]);
                maxSum = max(maxSum, sum);
        }
        return maxSum;
    }
};

算法二 divide and conquer

O(nlogn), 在leetcode上实际执行时间为18ms。

class Solution {
public:
    int maxSubArray(int A[], int n) {
        if (n <= 0) return INT_MIN;
        return helper(A, 0, n-1);
    }

    int helper(int A[], int left, int right) {
        if (left == right)
                return A[left];

        const int mid = left + (right-left) / 2;
        int sum = A[mid];
        int midMax = sum;
        for (int i=mid-1; i>=left; i--) {
                sum += A[i];
                midMax = max(midMax, sum);
        }

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

        const int leftMax = helper(A, left, mid);
        const int rightMax = helper(A, mid+1, right);

        return max(midMax, max(leftMax, rightMax));
    }
};

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

Maximum Subarray -- leetcode

原文：http://blog.csdn.net/elton_xiao/article/details/44131209