hdu1003(C++)解法1

#include<iostream>
using namespace std;
int Maxsum(int*a, int n);
int main()
{
int T,n,i,j,count=0,thissum,maxsum,redex1,redex0,redex2;
cin >> T;
while (T--)
{
count++;
int a[100000];
cin >> n;
for (i = 0; i < n; i++)
cin >> a[i];
cout<<"Case "<<count<<":"<<endl;
thissum =0,maxsum=a[0];
redex1 =redex0=redex2 =0;//redex0,redex1,redex3记录下标
thissum=0;maxsum=a[0];
for (i = 0; i < n; i++)
{
thissum+=a[i]; //从开始向右累加
if(thissum>maxsum)
{
redex1=redex0; //将redex1更新
maxsum=thissum;//将最大子序列更新
redex2=i; //记录末尾行标redex2
}
if(thissum<0){
thissum=0; //如果<0则这一序列不可能是后面增大，于是摒弃
redex0=i+1;//若这一位为止thissum<0那么redex0记录到下一位
}
}
cout<<maxsum<<" "<<redex1+1<<" "<<redex2+1<<endl;
if(T!=0)
cout<<endl;
}
}

巴特西

hdu1003(C++)解法1

最新文章

热门文章