http://acm.hdu.edu.cn/showproblem.php?pid=1231
Description
Input
Output
Sample Input
6 -2 11 -4 13 -5 -2 10 -10 1 2 3 4 -5 -23 3 7 -21 6 5 -8 3 2 5 0 1 10 3 -1 -5 -2 3 -1 0 -2 0
Sample Output
20 11 13
10 1 4
10 3 5
10 10 10
0 -1 -2
0 0 0
Huge input, scanf is recommended.
#include <cstdio> #include <cstring> #include <iostream> #include <cmath> #include<vector> #include<algorithm> using namespace std; #define PI 3.1415926 const int maxn=10007; const int INF=0x3f3f3f3f; int a[maxn]; int main() { int n; while(scanf("%d", &n), n) { for(int i=1; i<=n; i++) scanf("%d", &a[i]); int nows=1, Start=1, End=1; int sum, Max; sum=Max=a[1]; for(int i=2; i<=n; i++) { if(sum+a[i]<a[i]) { sum=a[i]; nows=i;///用来记录最大连续序列的开始的下标 } else sum+=a[i]; if(sum>Max) { Max=sum; Start=nows; End=i; } } if(Max<0)///如果全为负数的话，肯定最大值也为负数，只要有一个正数，就能找到最大连续子序列 printf("0 %d %d\n", a[1], a[n]); else printf("%d %d %d\n", Max, a[Start], a[End]); } return 0; }
原文：http://www.cnblogs.com/w-y-1/p/5748561.html