O(n) time O(1) space dynamic programming 8-line java solution with comment


  • 7
    M

    Define: sum[i] as the maximum subarray sum of [0...i], and this subarray MUST END WITH nums[i].

    (Some thought -- when facing "consecutive sequence problems" such as subarray or substring, the subproblems usually MUST END WITH current element, so that when NEXT element comes, the sequence will still remain consecutive).

    /*Then, from i --> i+1:
    -- if sum[i] >= 0, it gives non-negative contribution, sum[i+1] = sum[i] + a[i+1]
    -- if sum[i] < 0, it gives negative contribution, sum[i+1] = a[i+1]*/
    
    public class Solution {
        public int maxSubArray(int[] nums) {
            if (nums==null || nums.length==0) { return 0; }
            int max = nums[0], sum = nums[0];
            for (int i=1; i<nums.length; ++i) {
                if (sum >= 0) { sum += nums[i]; }
                else { sum = nums[i]; }
                max = Math.max(max, sum);
            }
            return max;
        }
    }

  • 0
    S
    This post is deleted!

Log in to reply
 

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