Maximum Subarray

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.

http://www.geeksforgeeks.org/archives/576
http://en.wikipedia.org/wiki/Maximum_subarray_problem

class Solution {//O(n)
public:
    int maxSubArray(int A[], int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (n < 1) return 0;
        int max = A[0];
        int sum = A[0];
        for(int ii = 1; ii < n; ++ii){
            sum += A[ii];
            if (A[ii] > sum) sum = A[ii];//the previous sum is negative, discard
            if (sum > max) max = sum;
        }
        return max;
    }
};

class Solution {//divide and conquer O(nlgn)
    int* a;//array
    int maxIndex;
    int leftPart(int end){//inclusive
        int sum = 0;
        int max = -9999;
        for(int ii = end; ii >= 0; --ii){
            sum += a[ii];
            if (max < sum){max = sum;}
        }
        return max;
    }
    
    int rightPart(int start){//inclusive
        int sum = 0;
        int max = -9999;
        for(int ii = start; ii >= maxIndex; ++ii){
            sum += a[ii];
            if (max < sum){max = sum;}
        }
        return max;
    }
    
    int getMax(int start, int end){
        if (start == end) return a[start];
        int half = (start+end)/2;
        int lrMax = max(getMax(start, half), getMax(half+1, end));
        return max(lrMax, leftPart(half)+rightPart(half)-a[half]);
    }
public:
    int maxSubArray(int A[], int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        maxIndex = n-1;
        a = A;
        return getMax(0,maxIndex);
    }
};