O(n) Solution and O(1) space


  • 1
    M

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

Log in to reply
 

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