有n个整数排成一圈，现在要从中找出连续的一段数串，使得这串数的和最大。

输入（标准输入）：第一行一个整数m,表示有m组数据。每组数据第一行一个整数n(n<=10^6)。第二行有n个整数，用空格隔开。

输出（标准输出）：对于每组数据输出一行三个整数p,x,y。表示从x到y的数串有最大和p。在多解情况下要求x最小，x相同的情况下y最小。保证p在长整范围。

Input:

1

3

1 2 -9

output:

3 1 2

代码

C++

#include<iostream> using namespace std; int q,n,a[100001]; int main() { cin>>q; for(int p=1;p<=q;p++) { long long ans=-0x7fffffff; int x,y; cin>>n; for(int i=1;i<=n;i++) {cin>>a[i];a[n+i]=a[i];} for(int i=1;i<=n;i++) { long long sum=0; for(int j=i;j<n+i;j++) { sum+=a[j]; if(sum>ans) { x=i; y=j; ans=sum; } } } cout<<ans<<' '<<x<<' '; if(y>n)cout<<y-n<<endl; else cout<<y<<endl; } return 0; }

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33

#include<iostream> using namespace std; int q,n,a[100001]; int main() { cin>>q; for(int p=1;p<=q;p++)    {       long long ans=-0x7fffffff;       int x,y;      cin>>n;      for(int i=1;i<=n;i++)         {cin>>a[i];a[n+i]=a[i];}       for(int i=1;i<=n;i++)       {          long long sum=0;          for(int j=i;j<n+i;j++)          {             sum+=a[j];             if(sum>ans)             {              x=i;              y=j;              ans=sum;             }         }         }         cout<<ans<<' '<<x<<' '; if(y>n)cout<<y-n<<endl;             else cout<<y<<endl;    } return 0; }

好像是因为没打高精，A不了，懒得写了