P1268 连续子段的最大和 OJ

题目描述

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

输入描述

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

输出描述

一行，子段的最大和。

样例输入

Copy to Clipboard

5 1 -3 4 1 -9 

样例输出

Copy to Clipboard

5

代码如下

#include 
#include 
#include using namespace std;/*
5
1 -3 4 1 -9*/
#define MIN -60001
int main()
{int n;while (cin >> n){vector DATA(n, 0);vector dp(n, 0);for (int i = 0; i < n; i++){cin >> DATA[i];}if (DATA[0]>=0){dp[0] = DATA[0];}int MAX = 0;int MAXIndex;int front;for (int i = 1; i < n; i++){if (dp[i-1]+DATA[i]>=0 ) {dp[i] = dp[i - 1] + DATA[i];}if (MAX<=dp[i]){MAX = dp[i];MAXIndex = i;}if (dp[i]==0){front = i;}}cout << MAX << endl;}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！