Java solution with explanation

  • 1


    Start with what you need. You need to get the maximum sum from a series of contiguous entries in the array. If the numbers are all positive, it is a no-brainer. Your max_sum is the sum of all the entries in the array. The reality is that your test cases will have a mix of positive and negative numbers. In that case, simply adding up all the numbers will not work.

    What is our most basic algorithm in this case? I started out with the following steps:

    Maintain some state for the current maximum.
    Keep track of the the sum while iterating through the array.
    If the sum is greater than max, set the max to be equal to the sum.
    Return max.
    One thing I am missing from the above is that we may need to reset the 'sum' based on some 'criteria'. But why?

    Lets go over the input provided in the problem description:
    [-2, 1, -3, 4, -1, 2, 1, -5, 4]

    If you keep summing the numbers without resetting the sum, you will end up in the following situation:

    Step 1: sum = -2 , max = -2
    Step 2: sum = -2 + 1 = -1, max = -1
    Step 3: sum = -1 + -3 = -4, max = -1
    Step 4: sum = -4 + 4 = 0, max = 0
    Step 5: sum = 0 + -1 = -1, max = 0
    Step 6: sum = -1 + 2 = 1, max = 1
    Step 7: sum = 1 + 1 = 2, max = 2
    Step 8: sum = 2 + -5 = -3, max = 2
    Step 9: sum = -3 + 4 = 1, max = 2

    The above breakdown spits out the max to be 2, but in reality the max is 6, from the subarray [4,-1,2,1].

    So where did we go wrong. We went wrong in step 1 itself. Having a negative number as a sum is a reminder that adding on to a sum that's already in the negative is simply making things worse because of the following situation:

    If your current sum is negative, you have two scenarios:

    The next number is positive
    The next number is negative
    If your next number is positive, you have simply made things worse by lowering the value of the next number by adding it to the negative number.

    If your next number is negative, by adding it to an already negative number you have lowered the value even further.

    Your best bet would be to simply scrap the sum, reset it to zero and add the current value to it.

    So the 'criteria' I was speaking above is the following:

    While summing the numbers if the sum turns out to be less than 0, reset the sum to be zero and continue with the process.

    So the code will look as follows:

    public int maxSubArray(int[] nums) {
    //Start with a sum and max variable
    int sum = 0;
    //Set the max to a really low value
    int max = Integer.MIN_VALUE;
    //Start iterating over all the numbers
    for(int i = 0; i < nums.length; i++) {
     int val = nums[i];
     //Add the val to the sum
     sum += val;
     //Check whether the sum > max, if so set the sum to be max
     max = (sum > max) ? sum : max;
     //If sum < 0, reset the sum to be 0
     sum = (sum < 0 ) ? 0 : sum; 
     //Return the max
     return max;
    Thats it!

  • 0

    What if the array is [-2, -1]?

    In this case, the correct answer is -1, however with your solution, you'd end up with an answer of 0, right?

  • 0

    @brandonkwleong I think you are wrong,he set the sum to zero not the max,so,the max end with -1

Log in to reply

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