最大子段和问题

最大子段和问题

分数 15

全屏浏览

切换布局

作者 王东

单位 贵州师范学院

最大子段和问题。给定由n个整数组成的序列，求序列中子段的最大和，若所有整数均为负整数时定义最大子段和为0。

输入格式:

第一行输入整数个数n（1≤n≤1000），再依次输入n个整数。

输出格式:

输出最大子段和。

输入样例1:

5
-2 11 -4 13 -5 -2

输出样例1:

20

代码长度限制

16 KB

时间限制

400 ms

内存限制

64 MB

#include <bits/stdc++.h>
using namespace std;
int main(){int n;cin>>n;int s[n+1];for(int i=1;i<=n;i++){cin>>s[i];}int sum=0;int besti=0,bestj=0;for(int i=1;i<=n;i++){int tempsum=0;for(int j=i;j<=n;j++){tempsum+=s[j];if(tempsum>sum){sum=tempsum;besti = i;bestj = j;}}}cout<<sum;return 0;
}