「动态规划」最大子数组和

力扣原题链接，点击跳转。

请在一个数组nums中找出一个子数组，使得这个子数组中所有元素的和最大。

你当然可以采取暴力枚举的方法，但是效率太低。这里我们用动态规划的思想来解决这个问题。首先确定状态表示：我们用dp[i]表示以i结尾的所有子数组的最大和。

接着推导状态转移方程。分类讨论：

• 如果以i结尾的子数组只包含nums[i]，那么和为nums[i]。
• 如果以i结尾的子数组长度大于1，那么和为dp[i-1]+nums[i]。

所以，dp[i]=max(nums[i],dp[i-1]+nums[i])。

接着考虑初始化的问题。显然dp[0]=nums[0]。填表时应按照从左往右的顺序。最终应返回整个dp表中的最大值。

class Solution {
public:int maxSubArray(vector<int>& nums) {// 创建dp表int n = nums.size();vector<int> dp(n);// 初始化dp[0] = nums[0];// 从左往右填表for (int i = 1; i < n; i++){dp[i] = max(nums[i], dp[i-1] + nums[i]);}// 返回整个dp表的最大值return *max_element(dp.begin(), dp.end());}
};

当然，你也可以在填表的同时把最大值求了。

class Solution {
public:int maxSubArray(vector<int>& nums) {// 创建dp表int n = nums.size(), ret = 0;vector<int> dp(n);// 初始化ret = dp[0] = nums[0];// 从左往右填表for (int i = 1; i < n; i++){dp[i] = max(nums[i], dp[i-1] + nums[i]);ret = max(ret, dp[i]);}// 返回整个dp表的最大值return ret;}
};