给出一个数列,要求:找出一个连续的数列,它们的和最大,Pascal语言实现.注意!数列最多可能有1000000000(10亿)个数,说明只能用O(n)的时间复杂度.是计算机的Pascal编程语言

来源:学生作业帮助网 编辑:六六作业网 时间:2024/12/24 09:17:36
给出一个数列,要求:找出一个连续的数列,它们的和最大,Pascal语言实现.注意!数列最多可能有1000000000(10亿)个数,说明只能用O(n)的时间复杂度.是计算机的Pascal编程语言给出一

给出一个数列,要求:找出一个连续的数列,它们的和最大,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:数据范围貌似错了吧。。)

收起

给出一个数列,要求:找出一个连续的数列,它们的和最大,Pascal语言实现.注意!数列最多可能有1000000000(10亿)个数,说明只能用O(n)的时间复杂度.是计算机的Pascal编程语言 给出一个数列1,2,3,4,5,.找出一个首项为4,公差为3的等差数列,并判断2001是不是这个数列的项 给出一个数列1,3,5,7,…,找出一个首项为3,公差为4的等差数列,并判断2013是不是这个数列的项 请你给出一个用递推公式表述的数列,使这个数列的极限为根号5. C语言题目,斐波那契数列菲波那契数列是指这样的数列:数列的第一个和第二个数都为1,接下来每个数都等于前面2个数之和.给出一个正整数a,要求菲波那契数列中第a个数是多少.输入要求第1行 编写一个C++程序,要求输出十之前的非斐波那契数列(Fibonacci)数列. C语言菲波那契数列问题描述菲波那契数列是指这样的数列:数列的第一个和第二个数都为 1,接下来每个数都等于前面 2 个数之和.给出一个正整数 a,要求菲波那契数列中第 a 个数是多少.输入第 C语言:数列的移动给定一个长度为N的连续数列,给M次操作,每次操作给定一个数K,要求把当前数列中的第K个数移动到数列最前面,用链表实现,输出M次操作后的数列.#include#include#define LEN sizeof(st C语言:移动数列给定一个长度为N的连续数列,给M次操作,每次操作给定一个数K,要求把当前数列中的第K个数移动到数列最前面,用链表实现,输出M次操作后的数列.#include#include#define LEN sizeof(struc 给出一个数列4,7,10,13,16,19,22...,问这个数列的第n项是什么?pascal 如果一个数列的平方收敛,那么这个数列本身是否收敛?收敛请证明?不收敛请给出反例. 请从数列2,4,10,14,56中找出一个与众不同的数 一个关于数列的难题, 求一个数列的和, 求一个数列的和, 在一个等差数列中,若有连续三项成等比数列,则这个数列的公差是0 matlab应该用哪个函数生成一个N个数的随机数列,且要求数列的平均值是M 什么是动态数列?试举一个时点数列的例子?