烟台h5网站建设,北京网页制作培训班,微微网站建设,网站建设：博采网络力扣原题链接#xff0c;点击跳转。
请在一个数组nums中找出一个子数组#xff0c;使得这个子数组中所有元素的和最大。
你当然可以采取暴力枚举的方法#xff0c;但是效率太低。这里我们用动态规划的思想来解决这个问题。首先确定状态表示#xff1a;我们用dp[i]表示以i…力扣原题链接点击跳转。
请在一个数组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(vectorint nums) {// 创建dp表int n nums.size();vectorint 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(vectorint nums) {// 创建dp表int n nums.size(), ret 0;vectorint 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;}
};
