53. Maximum Subarray (1)

Link

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Example:

Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

Follow up:

If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

Soluition

Dp作法是將問題簡化成 當下的最大sum會等於(之前的最大sum+目前的number

class Solution {
    public int maxSubArray(int[] nums) {
        int len = nums.length;
        //dp表示每個index的最大sum值
        //dp[i] = dp[i-1] + nums[i] 當dp[i-1] > 0,
        //若nums[i] < 0, 那就是dp[i] = dp[i-1]，因為加上nums[i]反而使sum變小
        int[] dp = new int[len];
        int maxValue = Integer.MIN_VALUE;
        for(int i = 0; i < nums.length; i++){
            dp[i] = nums[i] + ((i != 0 && dp[i-1] > 0) ? dp[i-1] : 0);
            maxValue = Math.max(maxValue, dp[i]);

        }
        return maxValue;
    }
}