Java 6 lines O(n) time + O(1) Space - Simple Explanation


  • 0
    J

    Given [-2,1,-3,4,-1,2,1,-5,4]

    1 ) We loop backward through the array. At each position, we consider what is the highest amount we can make.
    ex.

    i == 8) At the last position(4) the highest number we can make is 4.
    i == 7) we can choose -5 or (-5+4) so naturally we would choose (-5+4) = -1
    i == 6) we can choose 1 or (-5+4). We choose 1
    i == 5) we have 2 and from the previous result, we can also add 1 from (i == 6). So 2 + 1.
    i == 4) we have negative 1, but we can combine it with the previous result, so -1+(2+1) =2.
    i == 3) we have 4 and from the previous result 2. so 4+2 = 6***
    i == 2) cont....

    so we construct a new array using this algorithm: [2,4,3,6,2,3,1,-1,4]
    Grab the highest number and return.

    public class Solution {
        public int maxSubArray(int[] nums) {
            
            int max = nums[nums.length-1];
            for(int i = nums.length-2; i > -1; i--) {
                nums[i] = (nums[i+1] > 0) ? nums[i] + nums[i+1] : nums[i];
                if(nums[i] > max) max = nums[i];
            }
            return max;
            
        }
    }
    

Log in to reply
 

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