简单DP
#include <cstdio> #include <cstring> #include <iostream> using namespace std; int const MAXN = 100010; int a[MAXN]; int main(){ int t; while(~scanf("%d",&t)){ for(int k = 1;k <= t;k++){ int n; scanf("%d",&n); for(int i = 1;i <= n;i++){ scanf("%d",&a[i]); } int s = 0,l = 1,r = 1,pos1 = 1,pos2 = 1,s1 = -100; for(int i = 1;i <= n;i++){ if(s < 0){ s = a[i]; l = i; } else s += a[i]; if(s > s1){ s1 = s; pos1 = l; pos2 = i; } } printf("Case %d:\n",k); printf("%d %d %d\n",s1,pos1,pos2); if(k != t)printf("\n"); } } return 0; }