Elegant 6-line Java DP Solution


  • 0
    M

    dp[i] represents the max sum of sub array from some 'j' (j<i) to 'i', including 'i'

    public int maxSubArray(int[] nums) {
    	int max = nums[0];
    	int[] dp = new int[nums.length];
    
    	for (int i = 0; i < nums.length; i++) {
    		dp[i] = (i == 0 || dp[i - 1] <= 0) ? nums[i] : dp[i - 1] + nums[i];
    		max = dp[i] > max ? dp[i] : max;
    	}
    	return max;
    }

  • 0
    G

    That's cute, but you can make it with O(1) space.
    It's easy to see that you are only accessing the previous solution in each iteration. So essentially, you don't need to actually save all the previous results, just the last one.


Log in to reply
 

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