5 line Java Solution with O(1) space and O(n) time


  • 3

    Break this problem into n sub-problem: contiguous sub-sequence ending in index i.
    There are two options here:

    1. number at this index i: nums[i]
    2. number at this index + sequence before: nums[i-1]+nums[i]

    public class Solution {
        public int maxSubArray(int[] nums) {
            int max=nums[0];
            for(int i=1;i<nums.length;++i){
                nums[i]=nums[i-1]<0 ? nums[i] : nums[i-1]+nums[i];
                max = Math.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.