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

• 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;

}
}
``````

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