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.

Practice:

If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

Solution

algorithm that operates on arrays: it starts at the left end (element A[1]) and scans through to the right end (element A[n]), keeping track of the maximum sum subvector seen so far. The maximum is initially A[0]. Suppose we’ve solved the problem for A[1 .. i - 1]; how can we extend that to A[1 .. i]? The maximum

sum in the first I elements is either the maximum sum in the first i - 1 elements (which we’ll call MaxSoFar), or it is that of a subvector that ends in position i (which we’ll call MaxEndingHere).

MaxEndingHere is either A[i] plus the previous MaxEndingHere, or just A[i], whichever is larger.

1
2
3
4
5
6
7
8
9
10
11
12
13
14

public class Solution {
    public int maxSubArray(int[] nums) {
        int n = nums.length;
        if (n==0)
            return 0;
        int maxSoFar = nums[0];
        int maxEnding = nums[0];
        for (int i=1;i<n;i++){
            maxEnding = Math.max(nums[i],nums[i]+maxEnding);
            maxSoFar = Math.max(maxSoFar, maxEnding);
        }
        return maxSoFar;
    }
}