P1268 连续子段的最大和

题目描述

从一组数据（长度为 n，其中 n <= 10000，数据的值都大于 -60000）中找出连续的一段数，使得这段数的和最大。

输入描述

第一行是一个正整数 n，表示数据的个数，从第二行开始是 n 个数据。

输出描述

一行，子段的最大和。

样例输入

Copy to Clipboard

5 1 -3 4 1 -9 

样例输出

Copy to Clipboard

5 

 代码

#includeusing namespace std;
#define MAX 100
int dp[MAX];int main() {int n = 0;while (cin>>n){int *a = new int[n];for (int i = 0; i < n; i++)cin >> a[i];dp[0] = a[0];int MaxIndex = 0;for (int i = 1; i < n; i++){if (a[i] + dp[i-1] > 0) {dp[i] = dp[i - 1] + a[i];}else{dp[i] = 0;}if (dp[MaxIndex] < dp[i]) {MaxIndex = i;}}cout << dp[MaxIndex] << endl;}return 0;
}