O(n) Solution and O(1) space

• The idea is very simple.

• If previous continuous sum > 0, we can always achieve bigger number by adding to it.
• If previous continuous sum <0, we will always end up lowering the sum by adding to it. Hence, it is better to start the new sequence from that point.
While doing both above, we will keep track of maximum sum we have seen.
``````public class Solution {
public int maxSubArray(int[] nums) {
if(nums == null || nums.length == 0){
return Integer.MIN_VALUE;
}
// Maximum sequencese seen so far is the first element itself
int maxSeq = nums[0];
int prevSum = nums[0];
for(int i = 1 ; i < nums.length ; i++){
if(prevSum > 0){
// We can always get bigger number by adding to privious positive number
prevSum +=  nums[i];
}else{
// We can never get bigger value by adding in negative value
// We are better off starting new sequence from this point
prevSum = nums[i];
}
maxSeq = Integer.max(prevSum, maxSeq);
}
return maxSeq;
}
}
``````

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