hdu acm1003 这题交上去老是错的,望高手解答

发布网友发布时间：2024-10-01 10:04

共1个回答

热心网友时间：2024-10-08 20:28

这个我会。这道题的恶心之处，在于它会给出全为负的数据。比如 N=4, (-5, -6, -3, -2)，我单独处理了下这种情况，其余按最大连续子序列做就过了（方法自然是O(n)的动态规划）。

另外我觉得你的算法好像不对啊，你求出来的是从第一个元素起，和最大的子序列（最大前缀子序列），按你的做法，q-m永远等于1。
最后贴出我刚写的弱弱的代码。

int T,N;
int arr[100002];

int main(){
scanf("%d",&T);
for(int t=1;t<=T;t++){
scanf("%d",&N);
bool negtive=true;
for(int i=0;i<N;i++){
scanf("%d",&arr[i]);
if(arr[i]>0)
negtive = false;
}
int maxsum=0,sum=0,length=0,start=0,end=0;
if(negtive){
maxsum=10;
for(int i=0;i<N;i++){
if(maxsum==10 || arr[i]>maxsum){
maxsum = arr[i];
start=i+1;
end = i+1;
}
}
}
else{
for(int i=0;i<N;i++){
sum += arr[i];
if(sum>=0){
length++;
if(sum>maxsum){
end=i+1;
start = end-length+1;
maxsum = sum;
}
}
else{
sum = 0;
length=0;
}
}
}
printf("Case %d:\n",t);
printf("%d %d %d\n",maxsum,start,end);
if(t<T) printf("\n");
}
return 0;
}