[蓝桥杯][算法提高VIP]和最大子序列

题目 题解

经典动态规划之一。

dp[i] 表示以第i个元素结尾的子序列的最大值； 转移方程：当dp[i-1]>0时，前i个元素且以第i个元素结尾的最大子序列肯定要加上dp[i-1]，因为dp[i-1]可以对答案做出正贡献，因此dp[i] = a[i] + dp[i-1]；要是dp[i-1]>n; for(int i = 1;i >x; if(dp[i-1] > 0) dp[i] = dp[i-1] + x; else dp[i] = x; ans = max(ans, dp[i]); } cout