Maximum Subarray

LeetCode Source

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.

解法1：时间复杂度：O(n)，空间复杂度：O(1)

public int maxSubArray2(int[] A) {
        int newsum=A[0];
        int max=A[0];
        int start = 0;
        int end = 0;
        int currentStart = 0;
        int currentEnd = 0;
        for(int i=1;i<A.length;i++){
            if(newsum+A[i] >=A[i]) {
                currentEnd++;
                newsum = newsum + A[i];
            } else {
                newsum =  A[i];
                currentStart = i;
                currentEnd = i;
            }

            if(newsum > max) {
                max = newsum;
                start = currentStart;
                end = currentEnd;
            }

        }
        return max;
    }


    public int maxSubArray(int[] A) {
        int newsum=A[0];
        int max=A[0];
        for(int i=1;i<A.length;i++){
            newsum=Math.max(newsum+A[i],A[i]);
            max= Math.max(max, newsum);
        }
        return max;
    }

解法2：Divide And Conquer

1) Divide the given array in two halves
2) Return the maximum of following three
….a) Maximum subarray sum in left half (Make a recursive call)
….b) Maximum subarray sum in right half (Make a recursive call)
….c) Maximum subarray sum such that the subarray crosses the midpoint

References

1 Divide and Conquer | Set 3 (Maximum Subarray Sum)