给出一个数列,要求：找出一个连续的数列,它们的和最大,Pascal语言实现.注意!数列最多可能有1000000000（10亿）个数,说明只能用O（n）的时间复杂度.是计算机的Pascal编程语言
来源：学生作业帮助网 编辑：六六作业网 时间：2024/11/23 07:31:27
给出一个数列,要求：找出一个连续的数列,它们的和最大,Pascal语言实现.注意!数列最多可能有1000000000（10亿）个数,说明只能用O（n）的时间复杂度.是计算机的Pascal编程语言
给出一个数列,要求：找出一个连续的数列,它们的和最大,Pascal语言实现.
注意!
数列最多可能有1000000000（10亿）个数,说明只能用O（n）的时间复杂度.
是计算机的Pascal编程语言
给出一个数列,要求：找出一个连续的数列,它们的和最大,Pascal语言实现.注意!数列最多可能有1000000000（10亿）个数,说明只能用O（n）的时间复杂度.是计算机的Pascal编程语言
此题明显是要用一维动态规划：
max:=0;
for i:=1 to n do begin
if a[i-1]>0 then {a的下标要从0开始,方便处理}
a[i]:=a[i]+a[i-1];
if a[i]>max then
max:=a[i];
end;
write(max);
我服了550626557,这题的确要用滚动存储,不过看我的就当学多一种方法吧……
这个连续指什么。。自然数连续么。。
计算是不行的数据太大，所以用构造法。
简单点说就是构造一个符合条件的数列求和！
var
a,last,n,i,ans:longint;
begin
read(n);
last:=0;
ans:=-maxlongint;
for i:=1 to n do
begin
read(a);
inc(last,a);<...
全部展开
var
a,last,n,i,ans:longint;
begin
read(n);
last:=0;
ans:=-maxlongint;
for i:=1 to n do
begin
read(a);
inc(last,a);
if last>ans then ans:=last;
if last<0 then last:=0;
end;
writeln(ans);
end.
如上程序。
空间复杂度O(1)
时间复杂度O(n)
猥琐点来说，这是dp,但是滚动以后怎么看都是贪心！
收起
无视我吧。
（刚写了很多，仔细一想发现我脑残了，把问题想得太复杂，貌似不能删除回答，所以无视我吧。。。）
（Carl_xiao 和 550626557 都是正确的，只是注意下每次操作记得记录产生这个值的数列首项末项，如果答案要求输出数列段的话）
（PS：数据范围貌似错了吧。。）...
全部展开
无视我吧。
（刚写了很多，仔细一想发现我脑残了，把问题想得太复杂，貌似不能删除回答，所以无视我吧。。。）
（Carl_xiao 和 550626557 都是正确的，只是注意下每次操作记得记录产生这个值的数列首项末项，如果答案要求输出数列段的话）
（PS：数据范围貌似错了吧。。）
收起