Clear Java Solution with Explanation, O(1) Space


  • 3
    X

    The basic idea is to sum all the way from beginning to the end, if at any time the current sum is negative, reset to zero.

    Why?
    The concern only happens when we encounter a negative number. Then we have two options.

    1. Add the negative number into previous sum
    2. Reset the current sum to zero and start over from the next number

    Take a look at the below two examples

    Example 1
    1 2 3 4 -3 5 6
    When we encounter -3, previous sum is 10, currentSum will be 7 for option 1 and 0 for option 2.
    We would like to add -3 to the current sum and continue.

    Example 2
    1 2 -6 3 4
    When we encounter -6, previous sum is 3, currentSum is -3 for option 1 and 0 for option 2.
    We would like to start over from the next number 3,

    public class Solution {
        public int maxSubArray(int[] nums) {
            int max = nums[0];
            int currentSum = 0;
            for (int i : nums) {
                currentSum += i;
                max = Math.max(max, currentSum);
                if (currentSum < 0) {
                    currentSum = 0;
                }
            }      
            return max;
        }
    }
    

  • 0
    P

    @xyqshi What if all of numbers in this array are negative?


  • 0

    If all of numbers in this array are negative, "max = Math.max(max, currentSum);" makes "max" the Maximum negative.


Log in to reply
 

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