当前位置: 首页 > >

最大连续子序列(leetcode53)

发布时间:

思路

注意这是个 dp问题。
从最后一个数开始推。从后往前遍历每一个位置,dp[i]表示以该位置为起点的最大序列和。
有递归方程dp[i] = nums[i] + dp[i + 1] > 0 ? dp[i + 1] : 0


类似的思路

dp[i] = A[i] + (dp[i - 1] > 0 ? dp[i - 1] : 0);
dp[i]表示以该位置为终点的最大子序列


代码

class Solution {
public:
int maxSubArray(vector& nums) {
int n = nums.size();
if(n == 0)return -1;
int last = nums[n - 1];
int maxn = last;
for(int i = n - 2; i >= 0; i --)
{
last = last > 0 ? nums[i] + last : nums[i];
maxn = max(last,maxn);
}
return maxn;
}
};



友情链接: