P1115 最大子段和

题目描述

给出一个长度为 n 的序列 a，选出其中连续且非空的一段使得这段和最大。

输入格式

第一行是一个整数，表示序列的长度 n。

第二行有 n 个整数，第 i 个整数表示序列的第 i 个数字 ai​。

输出格式

输出一行一个整数表示答案。

输入输出样例

输入 #1

7
2 -4 3 -1 2 -4 3

输出 #1

4

解决方法

使用动态规划的思想，分解成小问题。

dp[i]表示以a[i]结尾的最大的子序列的和。（包含a[i]，这里是重点）

如果前面的值小于等于0，则直接dp[i] = a[i];

然后依次递推下去，每次都都结果进行更新

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 7;
int dp[MAXN], a[MAXN], n, ans;
//dp[i]是指以a[i]结尾的最大字段和int main()
{cin >> n;for (int i = 1; i <= n; i++)cin >> a[i];dp[1] = ans = a[1];//初始状态//递推for(int i = 2; i <= n; i++){if(dp[i - 1] > 0){dp[i] = dp[i - 1] + a[i];}else{dp[i] = a[i];}//dp[i] = dp[i - 1]>0? dp[i-1]+a[i] : a[i]ans = max(ans, dp[i]);}cout << ans;
}