O(n) Runtime O(0) Space - Java Solution with inline explanations


  • 0
    A

    Since we are looking for the greatest sum, +elem will always increase sum. If -elem, and has leftovers after (sum - elem), meaning the +leftover chunk still a chance to cumulate further upon encountering another +elem down the line. leftover + elem + elem > +elem + elem...

        public int maxSubArray(int[] nums) {
            int greatestSum = Integer.MIN_VALUE;
            int sum = 0;
            
            for (int i = 0; i < nums.length; i++) {
                // reset with curr elem
                // if +elem, gets rid of prev -debt; if -elem, no point decreasing further
                if (sum < 0) {
                    sum = nums[i];
                } else {
                    // if +elem, so always increasing anyways
                    // if -elem, but sum > 0 still +leftover, can be accumulated further with +elem down the line
                    sum += nums[i];
                }
                greatestSum = Math.max(greatestSum, sum);
            }
            
            return greatestSum;
        }
    

Log in to reply
 

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