Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
Re:我用的是最大子段和 DP 还是WA 不知道错哪里了In Reply To:我用的是最大子段和 DP 还是WA 不知道错哪里了 Posted by:y_zou at 2005-08-21 13:03:37 当输入两个数时,就错了。 输入: 1 2 -1 -2 输出为-1??? > /* > name: Maximum sum > author: Y_zou > time: 2005_8_21 > */ > > #include <iostream> > #include <cstdio> > > using namespace std; > int arrayB[50001]; > int arrayC[50001]; > > int MaxSum(int cnt,int* buff) > { > if(cnt<2) > return 0; > > arrayB[0] = 0; > arrayC[1] = 0; > for(int i=1;i <= 2; i++) > { > arrayB[i] = arrayB[i-1] + buff[i]; > arrayC[i-1] = arrayB[i]; > int max = arrayB[i]; > for(int j=i+1; j<=i+cnt-2; j++) > { > arrayB[j] = arrayB[j-1] > arrayC[j-1] ? arrayB[j-1]+ buff[j] : arrayC[j-1] + buff[j]; > arrayC[j-1] = max; > if(max < arrayB[j]) > max = arrayB[j]; > } > arrayC[i+cnt-2] = max; > } > int sum = 0; > for(int c=2; c<=cnt; c++) > { > if(sum < arrayB[c]) > sum = arrayB[c]; > } > return sum; > > > } > int main() > { > int Case,cnt; > int i; > int buff[50001]; > > scanf("%d",&Case); > for(int c=0; c <Case; c++) > { > if(c) > cout << endl; > scanf("%d", &cnt); > for(i=1; i <= cnt; i++) > { > scanf("%d",&buff[i]); > } > int sum = 0; > > if(cnt==2) > { > sum = buff[1] + buff[2]; > if(sum > buff[1] && sum > buff[2]) > cout << sum << endl; > else > { > if(buff[1] > buff[2]) > cout << buff[1] << endl; > else > cout << buff[2] << endl; > } > } > else > cout << MaxSum(cnt, buff) << endl; > } > > return 0; > } > Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator