Simple Java solution with explanation: O(1) space


  • 0
    D

    Array [A0,A1,...,An], define Sum(Ai) = A0+A1+...+Ai, then max sub sum ends with Ai equals Sum(Ai) - Min(Sum(A0), Sum(A1), ...Sum(Ai-1)). So this solution is to track the Min(Sum(A0), Sum(A1),..., Sum(Ai)) along the way and find max sub sum.

    public int maxSubArray(int[] nums) {
            if (nums == null || nums.length == 0) return 0;
            
            int minSum = 0; //the Min(Sum(A0), ..., Sum(Ai-1)) so far
            int sum = 0; //Sum(Ai)
            int result = nums[0];
            for(int i = 0; i < nums.length; i++) {
                sum += nums[i];
                result = Math.max(result, sum - minSum);
                minSum = Math.min(minSum, sum);                           
            }
            return result;
        }
    

Log in to reply
 

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