题目要求两段子序列和
分段就行 O(n)
话说这回数组又开小了,居然提示Runtime Error
Program P2479;
var
t,n,i,j,m,m2,p:longint;
a,b,c:array[0..50000] of longint;
begin
read(t);
a[0]:=-100001;
while (t>0) do
begin
read(n);
j:=0;
m:=0;
for i:=1 to n do
begin
read(a[i]);
if a[i]<0 then inc(j);
if a[i]>a[m] then m:=i;
end;
if j>n-2 then
begin
p:=a[m];
m2:=0;
for i:=1 to n do if (i<>m) and (a[m2]<a[i]) then m2:=i;
inc(p,a[m2]);
writeln(p);
end
else
begin
p:=0;
m:=-100001;
for i:=1 to n do
begin
inc(p,a[i]);
if (p<0) then p:=0;
if m<p then m:=p;
b[i]:=m;
end;
p:=0;
m:=-100001;
for i:=n downto 1 do
begin
inc(p,a[i]);
if (p<0) then p:=0;
if m<p then m:=p;
c[i]:=m;
end;
m:=0;
for i:=1 to n-1 do
if m<b[i]+c[i+1] then m:=b[i]+c[i+1];
writeln(m);
end;
dec(t);
end;
end.
分享到:
相关推荐
poj2479代码 Maximum sum 对于这道题,我的思路是先从左到右,计算并存储每个节点
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
poj分类poj分类poj分类poj分类
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
对于POJ1852题目和详细的解答,代码已经通过
西北工业大学POJ第二季习题,一共15题全部都有,便捷广大西北工业大学大一的孩子。
poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
poj 2329解题报告poj 2329解题报告poj 2329解题报告poj 2329解题报告
poj 1659解题报告poj 1659解题报告poj 1659解题报告poj 1659解题报告
北大POJ1159-Palindrome 解题报告+AC代码
这里我把自己对poj1276的理解和分析还有源代码都放在了里面,希望对大家有所帮助。谢谢
poj 百练 题目分类 poj 百练 题目分类
POJ1083的代码,POJ1083的代码,POJ1083的代码
北大POJ2586-Y2K Accounting Bug 解题报告+AC代码
poj 1001答案
POJ1503解答 POJ1503解答,正确答案(已通过POJ)
C语言 poj npu 西工大 C语言Poj答案全完整打包,给有需要的朋友
poj上的算法题目分类,对于大家想练习算法的同鞋可以参考一下,里面按类列出了各种算法的题号。