杭电acm1003题答案,运行成功就是不能AC

发布网友

我来回答

共1个回答

热心网友

经典的dp题， sum[i] = max(sum[i-1]+a[i], a[i]),找到所有sum的最大值即可
代码当时写麻烦了
#include<cstdio>
#define MAX 100500
#define inf 10000
using namespace std;
int a[MAX];
int main()
{
int t,n,i,j,cnt,max,ms,me,en,st,sum;
//freopen("1.txt","r",stdin);
scanf("%d",&t);
for(j=1;j<=t;j++) {
max=-inf;
scanf("%d",&n);
cnt=0;
for(i=0;i<n;i++){
scanf("%d",&a[i]);
if(a[i]<=0)
cnt++;
}
if(cnt>=n-1){
max=0;
for(i=0;i<n;i++){
if(a[i]>a[max])
max=i;
}
printf("Case %d:\n%d %d %d\n",j,a[max],max+1,max+1);
if(t>1&&j!=t)
printf("\n");
max=-inf;
continue;
}
i=0;
while(a[i]<=0)
i++;
while(i&&a[i-1]==0)
i--;
st=en=i;
sum=0;
max=-inf;
while(i<n){
if(i==0){
if(a[i]>=0){
sum=a[i];
st=en=i;
}
i++;
continue;
}
if(i&&a[i]>=0&&a[i-1]>=0){
sum+=a[i];
en=i;
if(sum>max){
max=sum;
ms=st;
me=en;
}
i++;
}
else if(i&&a[i]>=0&&a[i-1]<0){
if(sum>=0){
sum+=a[i];
en=i;
if(sum>max){
max=sum;
ms=st;
me=en;
}
i++;
}
else{
sum=a[i];
st=en=i;
if(sum>max) {
max=sum;
ms=st;
me=en;
}
i++;
}
}
else if(i&&a[i]<=0&&a[i-1]<=0){
sum+=a[i];
en=i;
i++;
}
else if(i&&a[i]<=0&&a[i-1]>0){
if(sum>max){
max=sum;
ms=st;
me=en;
}
sum+=a[i];
en=i;
i++;
}
}

printf("Case %d:\n%d %d %d\n",j,max,ms+1,me+1);
if(t>1&&j!=t)
printf("\n");
max=-inf;
}

return 0;
}