53. Maximum Subarray (1D-dp)

brute force

nested for loop, find each combination, 正數起點正數結尾(優化

time: O(n^2)

DP

經驗：從後面開始看, 固定一個數, 前面子序列會...?

maxsum數字(i), Max( 取前面的數max_sum（i-1) 或不取 (會是0) ) + 自身a[i]

1. subproblem : maxsum(i) = Max(max_sum(i-1), 0) + A[i]

2. f[i]

3. dp 方程:

max_sum = 自身最大 or 自身包含之前的sum的最大

f(i) = Max(A[i] , A[i] + f(i-1)) , 提出 A[i] =>

f(i) = Max(0, f(i-1) ) + A[i] . =>

也就是

dp[i] = nums[i] + (dp[i-1] < 0 ? 0 : dp[i-1]);

dp[i-1] < 0 的狀況 => 不取 = 0

time: O(n)

space: O(n)

class Solution { 
    public int maxSubArray(int[] nums) {
        // dp[i] = dp[i-1] < 0 ? 0 : dp[i-1];
        int dp[] = new int[nums.length];
        dp[0] = nums[0];
        int max = nums[0];
        for (int i = 1; i < nums.length; i++) {
            // dp[i] = nums[i] + (dp[i-1] < 0 ? 0 : dp[i-1]);
            // 自身最大 or 自身包含之前的sum的最大
            dp[i] = Math.max(nums[i], nums[i] + dp[i-1]);
            // dp[i] = nums[i] + Math.max(0, dp[i-1]); 提出 nums[i] 
            max = Math.max(max, dp[i]);
        }
        return max;
    }
}

DP - just use variable

dp[i] = nums[i] + Math.max(0, dp[i-1]);
can be
nums[i] = nums[i] + Math.max(0, nums[i-1]);

time :O(n)

space: O(1)

see notes!

class Solution { 
    public int maxSubArray(int[] nums) {
        int res = nums[0];
        int sum = nums[0];
        for (int i = 1; i < nums.length; i++) {
            // 自身最大 or 自身包含之前的 sum 的最大
            sum = Math.max(nums[i], sum + nums[i]);
            res = Math.max(res, sum);
        }
        return res;
    }
}

can be also wrote like this

class Solution {
    public int maxSubArray(int[] nums) {
        int max = nums[0];
        int presum = nums[0];
        for (int i = 1; i < nums.length; i++) {
            presum = Math.max(0, presum) + nums[i];
            max = Math.max(max, presum);
        }
        return max;
    }
}