前言

贪心章节第4篇。动态规划章节第10篇。同一题，两种方法。
记录 八十七【53. 最大子序和】

---

一、题目阅读

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组是数组中的一个连续部分。

示例 1：

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

示例 2：

输入：nums = [1]
输出：1

示例 3：

输入：nums = [5,4,-1,7,8]
输出：23

提示：

1 <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4

进阶：如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的 分治法 求解。

---

二、尝试实现

2.1 分析题目，确定方法

1. 题目含义有以下几点：

• 子数组是原来数组中的一个连续部分，说明数组nums保持原有顺序，不能排序，导致顺序改变；
• 只说找到连续子数组的最大值，这个连续子数组中元素个数是多少不确定；
• 从哪个元素开始构建连续子数组也不知道。

2. 不过想求最大和，那么这个连续子数组中应该正数之和尽可能大，负数之和尽可能大。用滑动窗口能否解决？……（滑动窗口，没想好移动规则）
3. 暴力求解。时间复杂度肯定高，根据提示的nums.length预判一定超时。不过按照暴力遍历写出一份代码。如下：
   分析时间复杂度：循环次数有n*(n+1)/2，所以是O(n ²)。提交后：超时。

   class Solution {
   public:int maxSubArray(vector<int>& nums) {int result = INT_MIN;for(int i = 0;i < nums.size();i++){int sum = 0;for(int j = i;j < nums.size();j++){sum += nums[j];result = max(result,sum);}}return result;}
   };
   

4. 滑动窗口应该是正确的思路。但是没想出移动规则。

---

三、参考学习

【53. 最大子序和】 贪心思路参考学习链接

3.1贪心思路

1. 连续和+nums[i]：如果连续和是负数，那么nums[i]会变小，再往后加值，已经拖累了总和。所以：当连续和=负数，从nums[i]作为新起点，重新开始。
2. 如果连续和是正数，后面的值+连续和，对后面的值起增大作用。
3. 模拟过程：箭头代表，由于连续和为正，扩展区间。同时用result记录过程中的最大值。没有箭头，更换颜色，代表连续和为负，更新起点。
   

3.2 代码实现【贪心】

在暴力解法的基础上改：

class Solution {
public:int maxSubArray(vector<int>& nums) {int result = INT_MIN;int sum = 0;for(int i = 0;i < nums.size();i++){if(sum < 0){sum = 0;}sum += nums[i];result = max(result,sum);}return result;}
};

3.3 动态规划思路【分治法】

3.3.1 沿用贪心的思路——推动态规划实现

1. 指明动态规划也可求解。那么就需要去找状态转移过程。
2. 定义dp数组和下标的含义：

• dp数组大小和nums数组大小相等；
• dp[i]：当以nums[i]作为子序列的最后一个元素（包含nums[i]），最大的连续子序列和为dp[i]。

3. 状态转移过程：（思路还是用贪心的思路）

• 如果dp[i-1] < 0，那么重新开始。dp[i] = nums[i]。
• 如果dp[i-1] > 0，那么dp[i] = dp[i-1]+nums[i]；
• 同时用一个result记录过程中的dp数组中的最大值。

4. dp初始化：dp[0] = nums[0]；
5. 遍历顺序：从递推公式看，从前往后。
6. 总结：贪心中用int sum来保存连续和。此处用dp数组来保存连续和。

3.3.2代码实现【动态规划】

class Solution {
public:int maxSubArray(vector<int>& nums) {vector<int> dp(nums.size(),0);//初始化dp[0] = nums[0];int result = nums[0];for(int i =1;i < nums.size();i++){if(dp[i-1] < 0) dp[i] = nums[i];//重新开始else {dp[i] = dp[i-1]+nums[i];}result = dp[i] > result ? dp[i]:result;}return result;}
};

3.3.3动态规划参考思路

【53. 最大子序和】 动态规划参考详解

1. dp数组含义一致：dp[i]：当以nums[i]作为子序列的最后一个元素（包含nums[i]），最大的连续子序列和为dp[i]。
2. 递推公式：只有两种情况

• 第一种：把nums[i]囊括到之前的子序列中，dp[i-1] + nums[i]；
• 第二种：从nums[i] 重新开始子序列。nums[i]。
• 所以取最大值：max(nums[i] , dp[i-1] + nums[i])。

3. 初始化：dp[0] = nums[0].
4. 遍历顺序：从前往后，根据递推公式。
5. return dp数组中的最大值。
6. 代码实现和**3.3.2代码实现【动态规划】**一致。

---

总结

（欢迎指正，转载标明出处）