Accepted O(n) solution in java


  • 242

    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;
    }

  • 8
    F

    Similar idea, reset if left sum is a negative value.

    class Solution {
    public:
        int maxSubArray(int A[], int n) {
            int maxSub = INT_MIN;
            int leftPositive = 0;
            for (int i = 0; i < n; i++) {
                maxSub = max(maxSub, leftPositive + A[i]);
                leftPositive = max(0, leftPositive + A[i]);
            }
            return maxSub;
        }
    };

  • 3
    K

    Kadane's algorithm


  • 7

    Hi, flyflybird. I happen to have a similar code :-)

    class Solution { 
    public:
        int maxSubArray(vector<int>& nums) {
            int sum = 0, smax = INT_MIN;
            for (int num : nums) {
                sum += num;
                if (sum > smax) smax = sum;
                if (sum < 0) sum = 0;
            }
            return smax;
        }
    };

  • 13

    Even masters in computer science solved LeetCode problems in the past :-)


  • 2
    S

    Best and most clear approach that you can ever get. If still in doubt, check this video tutorial on Kaden's algorithm.
    https://www.youtube.com/watch?v=epTQfFlhQBo


  • 6
    L

    Thanks for the explanation, good idea.

    I think we should also consider if (nums == null || nums.length == 0);


  • 1
    L

    Elegant solution!


  • 0
    D
    Who can tell me which is better,  Jon Bentley's Code is more efficient than the code below? WHY?
    
    
    int maxSubArray(int* nums, int numsSize) {
        register int cur = 0;
        register int max = INT_MIN;
        for(int i = 0; i < numsSize; i++){
            cur += nums[i];                          // greedy to add num untill it smaller than 0
            max  = cur > max ? cur : max;        // mark the max val during the adding
            if(cur < 0)
                cur = 0;
        }
        return max;
    

    }


  • 0
    R

    clear explanation . thanks for share


  • 1
    R

    your explanation is excellent.

    we can do the same with this relation

    sum(0,i) = a[i] + (sum(0,i-1) < 0 ? 0 : sum(0,i-1))

    this equation says that if previous sum is negative then no need to carry on with current sum=previous sum+current element since it will give lesser sum then the sum restarted with current element.

    int maxSubArray(vector<int>& nums) {
            int n=nums.size();
            int max=nums[0],sum=nums[0];
            for(int i=1;i<n;i++){
                sum=((sum<0)?0:sum)+nums[i];
                max=sum>max?sum:max;
            }
         return max;
        }

  • 0
    H

    @cbmbbz this can go wrong if there is only one negative number in the array.


  • 0
    D
        public int maxSubArray(int[] nums) {
            int maxSum = nums[0];
            int sum = nums[0];
            for (int i = 1; i < nums.length; i++) {
                sum = Math.max(sum + nums[i], nums[i]);
                maxSum = Math.max(maxSum, sum);
            }
            return maxSum;
        }
    

  • 0
    C
    This post is deleted!

  • 2
    C
    public int maxSubArray(int[] nums) {
        
        int n = nums.length;
        int max = nums[0];
        int sum = nums[0];
        int i = 1;
        
        while (i < n) {
            sum = Math.max(sum, 0);
            max = Math.max(sum + nums[i], max);
            i++;
        }
        
        return max;
    }

  • 0
    J

    nice solution~~~


  • 0
    M

    When found a potential subarray, maxEndingHere is not cleaned, so it won't count right for second potential subarray, for example in this test case -2,1,-3,4,-1,2,1,-5,4,1,2,1,4, your program will output 13 which contains 1 from history.


  • 2

    interesting fact: a problem solved by a computer professor in 1984, now become an easy level problem in Leetcode in 2016/2017...


  • 0
    This post is deleted!

  • 0
    R
    This post is deleted!

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.