這一題不算難，確定最大值容易，掃描一遍數組即可得，時間復雜度是O(N)，結束的地方也好確定，隨著max更新就可以了。最難確定的是開始的界low，為此多花了不少冤枉時間！為了確定low，可以像確定high那樣再掃描一遍，不過這次要倒著掃描，從high開始，這兩個過程幾乎是對稱的。
#include<stdio.h>
#define M 100010
#define MIN 10000
int main()
{
int T,i;
scanf("%d",&T);
for(i=1;i<=T;i++)
{
int N,low,high;
long max=-MIN,partsum=0;
int num[M];
scanf("%d",&N);
int j;
for(j=0;j<N;j++)
scanf("%d",&num[j]);
for(j=0;j<N;j++)//正著掃描，確定上界high
{
partsum+=num[j];
if(partsum>max)
{
max=partsum;
high=j;
}
if(partsum<0)
{
partsum=0;
}
}
int partsum2=0,max2=-MIN;//這一遍倒過來掃描，確定下界low
for(j=high;j>=0;j--)
{
partsum2+=num[j];
if(partsum2>=max2)
{
max2=partsum2;
low=j;
}
if(partsum2<0)partsum2=0;
}
if(j==0)low=0;
printf("Case %d:\n",i);
printf("%d %d %d\n",max,low+1,high+1);
if(i!=T)printf("\n");
}
}
花了兩個多小時的時間，WA了5次，AC的那一刻實在很爽，相信這也是每個ACMer的原動力所在吧。
posted on 2011-08-19 21:56
小鼠標 閱讀(200)
評論(0) 編輯 收藏 引用