题目描述
给你一个整数数组
nums，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。子数组
是数组中的一个连续部分。
示例 1：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
思路：
题目意思很简单，最暴力的两层遍历然后取最大的那个值，能出结果，但肯定会超时。
class Solution { public: int maxSubArray(vector<int>& nums) { int f=-1e9; for(int i=0;i<nums.size();i++){ int res=0; for(int j=i;j<nums.size();j++){ res+=nums[j]; f=max(f,res); } } return f; } };
如何不超时呢，题目要求我们是不需要给出子序列的，只需要最大值即可。那么其实就到了动态规划擅长的地方了，也不需要怕动态规划，这个题还是很简单，各位读者往下看。
很简单的道理：和负数相加总和会变小，和正数相加总和会变大
- 定义状态：设定一个状态数组 dp，其中 dp[i] 表示以第 i 个元素结尾的最大子数组和。
- 状态转移方程：dp[i] = max(dp[i-1] + nums[i], nums[i])，即要么将当前元素加入到之前的子数组中，要么以当前元素开始一个新的子数组。
- 最终结果：遍历 dp 数组，找到其中的最大值，即为最大子数组和。
两种版本的代码：
class Solution { public: int f[100005]; // 定义一个数组 f，用于存储以当前元素结尾的最大子数组和 int maxSubArray(vector<int>& nums) { f[1] = nums[0]; // 初始化 f[1] 为第一个元素的值 // 遍历数组 nums，计算以当前元素结尾的最大子数组和 for(int i = 2; i <= nums.size(); i++) { if(f[i - 1] >= 0) f[i] = f[i - 1] + nums[i - 1]; // 若前一个元素结尾的子数组和大于等于 0，则将当前元素加入子数组中 else f[i] = nums[i - 1]; // 否则，以当前元素开始一个新的子数组 } int res = f[1]; // 初始化最大子数组和为数组第一个元素的值 // 找到 f 数组中的最大值，即为最大子数组和 for(int i = 2; i <= nums.size(); i++) res = max(res, f[i]); return res; // 返回最大子数组和 } };
简洁版本：
class Solution { public: int maxSubArray(vector<int>& nums) { int res = nums[0]; // 初始化最大子数组和为第一个元素的值 for(int i = 1; i < nums.size(); i++) { if(nums[i - 1] >= 0) // 如果前一个元素结尾的子数组和大于等于 0 nums[i] += nums[i - 1]; // 将当前元素加入到前一个子数组中 if(nums[i] > res) // 如果当前子数组和大于最大值 res = nums[i]; // 更新最大值为当前子数组和 } return res; // 返回最大子数组和 } };
