题目链接:leetcode最大子数组和
目录
题目让我们找出一个具有最大和的连续子数组,返回其最大和。
先创建一个dp表
首先先思考dp表里面的值所表示的含义(是什么?)
dp[i]表示在i位置连续子数组和的最大值
这种状态表示怎么来的?
1.经验+题目要求
经验:以i位置为结尾
题目要求返回其最大和;
dp[i]等于什么?
用之前或者之后的状态,推导出dp[i][j]的值;
根据最近的最近的一步,来划分问题
这里我们分两种情况讨论:
情况一:当连续子数组的长度==1
那么此时dp[i]就应该等于该位置的值,即num[i];
所以得:dp[i]=num[i];
情况一:当连续子数组的长度>1
此时我们应该用i-1位置的最大和再加上i位置的值(num[i]),
而“i-1位置的最大和”就是dp[i-1]
所以得dp[i]=dp[i-1]+num[i]
综上:
题目需要最大值,所以要取这两者的最大值:
即:dp[i]=max(num[i],dp[i-1]+num[i])
(保证填表的时候不越界)
根据状态转移方程,我们需要初始化dp[i-1]
这里我们采用创建虚拟节点的方式:
为了不让dp[0]影响后续的值,
所以dp[0]=0;
(为了填写当前状态的时候,所需要的状态已经计算过了)
这里所需要的状态是:i-1
所以从左到右
(根据题目要求和状态表示)
综上分析:
返回值为:和最大值
class Solution {
public:
int maxSubArray(vector<int>& nums) {
//1.创建dp表
//2.初始化
//3.填表
//4.返回结果
int n=nums.size();
vector<int> dp(n+1);
int ret=INT_MIN;
for(int i=1;i<n+1;i++)
{
dp[i]=max(dp[i-1]+nums[i-1],nums[i-1]);
ret=max(ret,dp[i]);
}
return ret;
}
};