var

left,mr,ml,i,j,k,l,n,m:longint；

max:int64；

a,b,c,f:array[0..10000] of longint；

begin

readln(n)；

for i:=1 to n do

read(a[i])；

max:=-9999999；

for i:=1 to n do

if a[i]>max then

max:=a[i]；

if max<0 then

begin

write(max)；

halt；

end；

for i:=n+1 to 2*n do

a[i]:=a[i-n]；

f[0]:=0；left:=1；max:=0；

for i:=1 to 2*n do

begin

f[i]:=f[i-1]+a[i]；

if f[i]<0 then

begin

left:=i+1；

f[i]:=0；

end；

if (f[i]>max)and(i-n<left) then

begin

max:=f[i]；

mr:=i；

ml:=left；

end；

if (f[i]>max)and(i-n>left) then

break；

end；

write(max)；

end.

为何超时

搜索必然超时,要用动规

如何用动归

max{最大和,总和-最小}

f[i]表示:前i个数(必须取第i个数)的最优值.

f[i]:=a[i]；

if f[i-1]>0 then inc(f[i],f[i-1])；

我说一种比较容易理解的方法（和dp有些许差别）

只需要扫描一边，时间 O(n)，空间 O(1)

设S为加到目前的值，那么程序可以写做：

readln(n)；

ans := - maxlongint；

S := 0；

for i := 1 to n do

begin

read(a)；

inc(S, a)；

ans := max(S, ans)；

if S < 0 then

S := 0

end；

基本的思想是，如果加到目前为止的 S 是正数，那么它肯定对后面的数有所帮助，就继续加；如果 S 是负数，那还不如前面加的所有数都不要了，从下一个数开始加算了。

这题跟最大加权矩形、吃西瓜共同构成这一类问题的一维、二维和三维情况。

和我(你头上那位)一样嘛

我可能想错了,这是个环

状态: Accepted

测评机： Xeost[5]

得分： 100分

提交日期： 2008-7-26 21:03:00

有效耗时： 该状态没有记录

测试结果1: 测试结果正确

测试结果2: 测试结果正确

测试结果3: 测试结果正确

测试结果4: 测试结果正确

测试结果5: 测试结果正确

测试结果6: 测试结果正确

测试结果7: 测试结果正确

测试结果8: 测试结果正确

测试结果9: 测试结果正确

测试结果10: 测试结果正确