| ||||||||||
| 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