Question

杭电 ACM HDU 1231 谁能出个测试案例找到错误..我不知道哪里出错了 一直WA

#include <stdio.h>
#include<iostream>
#include <string>
#include <fstream>
using namespace std;
int maxnum(int *a,int &begin,int &end,int len)
{
int i,max=-65534,temp[1001],ep=0,bp=len-1,eep;
for(i=0;i<len;i++) if(a[i]>=0) { bp=i; if(a[i]!=0) break;}
for(i=len-1;i>=0;i--) if(a[i]>=0) { ep=i; break;}
if(ep<bp)
{
begin=a[0];
end=a[len-1];
max=0;
return max;
}
else if(ep==bp)
{
begin=a[bp];
end=a[bp];
max=a[bp];
return max;
}
else
{
temp[0]=a[bp];
for(i=1;i<=ep-bp;i++) temp[i]=temp[i-1]+a[bp+i];
for(i=0;i<=ep;i++)
if(temp[i]>max)
{
max=temp[i];
end=a[bp+i];
eep=i;
}
temp[0]=max;
for(i=1;i<=ep;i++) temp[i]=temp[i-1]-a[bp+i-1];
max=-65534;
for(i=0;i<=eep;i++)
if(temp[i]>max)
{
max=temp[i];
begin=a[bp+i];
}
return max;
}
}
int main()
{
int arrays[1001],beginp,endp,n,i,res;
fstream cin("2.txt");
while(cin>>n)//scanf("%d",&n) && n)
{
beginp=endp=0;
for(i=0;i<n;i++) cin>>arrays[i];//scanf("%d",&arrays[i]);
res=maxnum(arrays,beginp,endp,n);
printf("%d %d %d\n",res,beginp,endp);
}
return 0;
}

Answer 1

42
698 661 -893 41 -724 -683 -769 -67 -956 955 113 -592 365 -279 -148 -934 815 -75
-747 187 -281 -763 599 562 -147 -249 728 -547 18 -188 -37 -111 -343 -107 888 -85
1 -808 -106 521 -854 638 -213
//你的答案
1359 698 661
//正确答案
1493 599 728

其他测试数据
48
-657 -467 -736 125 -649 -41 969 896 -27 907 -519 -63 -954 94 928 9 -787 439 -807 896 949 -713 -155 815 101 118 981 -207 949 -752 -788 175 -768 -336 -988 -324 -133 380 928 765 -203 801 850 110 383 672 463 481
5
617 -321 -248 -849 -313
36
-427 26 -899 -162 -432 -86 -49 -43 -56 -868 83 471 526 582 985 -645 319 -694 970 485 -224 -534 733 155 -578 590 944 -839 70 -379 -524 -491 275 952 121 -699
32
-267 -243 255 940 -614 -353 -735 -6 -112 -583 -478 -68 331 -499 313 878 191 478 829 90 37 930 -707 307 414 -89 417 -143 -201 308 944 511
14
866 -461 -639 -253 -245 618 -790 274 -991 -850 797 -351 -670 -906
31
-987 570 -546 699 282 633 565 -809 147 871 -747 71 894 566 713 -960 123 407 154 832 911 655 -950 -572 -284 491 -523 297 -557 865 -348
47
-123 -935 -716 -790 -810 -579 -937 -886 923 -67 -822 -675 -491 645 -154 49 119 131 -806 -207 -91 -397 681 17 445 -946 -112 -902 234 -637 715 -89 -250 -284 -279 79 -736 740 -291 -189 639 -97 870 -86 22 -693 -47
13
280 -978 669 572 -819 400 -769 -759 22 -718 520 54 -979
10
-764 -151 161 -798 -316 273 417 280 -978 -84
15
679 386 183 -554 -608 705 167 -890 225 -662 616 112 461 -747 -828
27
992 419 -394 -859 830 -395 -16 -643 -101 -228 953 -800 -656 817 -133 825 925 839 668 976 282 -627 523 443 -189 408 -274
41
211 129 314 630 623 923 -686 874 -666 743 -557 147 344 267 -672 806 -219 512 -695 -560 -73 715 721 442 -557 63 -304 -708 -452 -927 358 -458 -616 76 978 -403 311 742 -910 -397 -895
40
859 -405 0 -264 796 -933 -786 658 910 50 671 -744 814 316 114 -290 766 772 -636 668 552 -759 -970 143 677 980 657 878 -498 121 -809 -993 833 -676 27 891 -427 -474 -653 335
44
136 -931 149 74 -753 80 -382 620 713 884 817 700 231 -27 976 427 -77 -348 474 -67 163 414 -795 -534 -321 -255 -804 997 528 -803 -545 108 505 727 -935 -785 -245 -28 851 580 275 -109 56 -151
45
651 -711 -20 -639 984 193 -808 -198 912 11 369 795 171 -973 -942 896 786 -934 -27 -546 647 126 67 231 966 -855 -228 -661 -134 -327 -599 593 514 928 592 486 -731 381 903 53 133 43 -115 -631 480
31
566 559 988 -488 -219 303 -940 -101 351 -453 -754 765 525 345 448 -132 -126 -642 322 -497 254 -20 -716 -939 -654 -195 -701 284 325 816 -919
32
215 -380 -781 -494 356 931 823 168 -629 145 -155 341 -97 -12 -259 825 -627 662 -623 525 927 -616 269 545 385 -646 484 -987 -958 345 -532 572
41
824 206 286 329 -830 23 -67 318 -594 338 -198 473 756 9 -55 -574 720 -935 -430 -389 661 -378 -711 -229 403 303 576 588 -277 -92 -356 -142 786 -779 997 302 949 140 -590 273 -643
32
980 -923 627 -323 -158 -856 -379 -687 -490 -726 -135 -327 501 378 -703 381 -780 -213 671 54 969 845 299 848 80 841 -316 -418 -737 365 -876 639
37
-247 -633 -368 -419 -7 -676 -638 -879 852 -692 445 301 196 251 -811 -279 663 -995 492 -548 -811 -437 216 805 787 -186 -778 140 680 -917 -145 -472 814 -696 -310 -557 859
0
//////////////////////////////////////////////参考答案////////////////////////////////////////////////////
6535 969 481
617 617 617
4168 83 944
5507 313 511
866 866 866
6031 570 655
923 923 923
1241 669 572
161 161 161
1248 679 183
5757 817 408
4273 211 442
6227 658 878
5900 620 414
3895 593 43
2113 566 988
3884 356 385
3398 403 140
980 980 980
1353 852 251

Answer 2

没什么好说，就跟那个最长不下降子序列一个想法，只不过是连续的，其实更好想

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct NODE
{
int value;
int qianqu;
int max;
}node[10005];

int main()
{
int n,i,j,k,l;
while(scanf("%d",&n),n)
{
for(i=0;i<n;i++)
{
scanf("%d",&node[i].value);
node[i].qianqu=node[i].value;
node[i].max=node[i].value;
}
for(i=1;i<n;i++)
{
if(node[i].max<=node[i-1].max+node[i].value)
{
node[i].qianqu=node[i-1].qianqu;
node[i].max=node[i-1].max+node[i].value;
}
}
for(i=n-1,j=-1,k=-1;i>=0;i--)
if(node[i].max>=j)
{
j=node[i].max;
k=i;
}
if(j==-1)printf("%d %d %d\n",0,node[0].value,node[n-1].value);
else printf("%d %d %d\n",j,node[k].qianqu,node[k].value);
}
}