Java O(n)


  • 0
    U
    1. Sweep the initial negative numbers to find a maximum negative number to return in case the array is all nonzero.
    2. When you get past the initial stream of negative numbers, repeatedly
    • add all the consecutive nonnegative numbers. Once finished compare to the max, store if greater than max.
    • add all the negative numbers to previous summation. Once it goes below zero, skip the rest of them (no reason to carry them on)
       public int maxSubArray(int[] nums) {
            int max = Integer.MIN_VALUE;
            
            int sum = 0, i = 0; 
            while (i < nums.length && nums[i] < 0) {
                if (nums[i] > max) 
                    max = nums[i]; 
                i++;
            } 
            
            while (  i < nums.length ) {
                 for (  ; i < nums.length && nums[i] < 0; i++) {
                    if (sum > 0) 
                        sum = sum + nums[i];
                 }
                 
                 if (sum < 0)  sum = 0; 
                 
                 for (  ; i < nums.length && nums[i] >= 0; i++) {
                    sum = sum + nums[i];
                }
                
                if (sum > max) max = sum; 
            }
            
            return max; 
        }
    

Log in to reply
 

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