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.

Idea:

Go through the list one by one and there are three cases:

• case 1: adding this number keep the current sum larger than 0, then add it to current sum.
• case 2: the number itself is larger than current sum and current sum is less than 0, replace the number with current sum.
• case 3: adding the number makes sum less than 0, replace the current sum with next number.

The key idea is that adding a number makes the current sum less than 0 will garantee that the maximum sub array does not include this number.

Solution:

public class Solution {
    public int maxSubArray(int[] nums) {
        if(nums == null || nums.length == 0) return 0;
        // use int k to specify v
        int k = 0,pre_sum = 0,current_sum =nums[0], max = current_sum;
        for(int i = 1; i < nums.length; i++){
            if(nums[i] > current_sum && current_sum < 0) current_sum = nums[i];
            else if(nums[i] + current_sum >= 0) current_sum = current_sum+nums[i];
            else{ if(++i < nums.length) current_sum = nums[i];}
            max = Math.max(current_sum, max);
        }
        return max;
    }
}

A better solution:

@cbmbbz said in Accepted O(n) solution in java:

this problem was discussed by Jon Bentley (Sep. 1984 Vol. 27 No. 9 Communications of the ACM P885)

the paragraph below was copied from his paper (with a little modifications)

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.

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