My Ninety-fifth Page - 最大子序和 - By Nicolas

这篇page是针对leetcode上的53.最大子序和这道题所写的。小尼简单的说明一下这道题的意思，给定一个整数数组nums，需要给出一个具有最大和的连续子数列，返回其最大值。

小尼简单的说明一下这道题的动态规划五部曲：

1.确定dp数组（dp table）以及下标的含义

dp[i]：包括下标i之前的最大连续子序列和为dp[i]。

2.确定递推公式

dp[i]只有两个方向可以推出来：

• dp[i - 1] + nums[i]，即：nums[i]加入当前连续子序列和
• nums[i]，即：从头开始计算当前连续子序列和

一定是取最大的，所以dp[i] = max(dp[i - 1] + nums[i], nums[i]);

3.dp数组如何初始化

从递推公式可以看出来dp[i]是依赖于dp[i - 1]的状态，dp[0]就是递推公式的基础。

dp[0]应该是多少呢?

根据dp[i]的定义，很明显dp[0]应为nums[0]即dp[0] = nums[0]。

4.确定遍历顺序

递推公式中dp[i]依赖于dp[i - 1]的状态，需要从前向后遍历。

5.推导出dp数组

小尼接下来拉一下这道题的解题的代码：

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

希望上面的代码可以帮助到小伙伴们~~~