[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.

click to show more practice.

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.

This problem took me 2 hours to finish. At first, I was thinking this in a DP way, but failed. Then I used two pointers: start and end. The key is when to move start and when to move end.

1. when the current sum value <= 0,  move start. 1) if end is positive, move start to end, else move start to end+1.

2. when current sum value > 0, keep start and move end backwards, as this sub-array would give positive contribution.

My Code :

 int maxSubArray(int A[], int n) {
        int s = 0, e = 0;
        int curval = 0, maxval = INT_MIN;
        int maxs = 0, maxe = 0;
        while(e < n){
            curval = curval + A[e];
            if(curval > maxval){
                maxval = curval;
                maxs = s;
                maxe = e;
            }
            if(curval < 0){
                if(A[e] > 0){
                    s = e;
                    e = s;
                } else{
                    s = e + 1;
                    e = s;
                }
                curval = 0;
            } else {
                e = e + 1;
            }
        }
        return maxval;
    }

=============However, the divide and conquer result is still not finished!=======