最大子段和
老师给乐乐布置了一份作业, 乐乐不知如何解决,找你帮忙解决。老师给一串很长的数列,要求从中找出连续的一段来使得总和最大。
输入:第一行包括一个整数 n,表示数列长度为 n (n<=100000) 。
第二行包括 n 个整数来描述这个数列,每个整数的绝对值不超过 1000。
输出:只有一个整数,为最大的连续段总和。
样例输入:
5
1 -2 3 1 -4
样例输出:
4
算法分析:设 b[i]为以第 i个位置的数结尾的连续的最大子段和,若 b[i-l]大于 0,显然 ,b[i]=b[i-l]+a[i]; 如果 b[i-1] 小于 0,则b[i]=a[i],这里应用了一个贪心思想。通过枚举从第 1 个到第 n 个数结尾的连续的最大子段和,就可以求出所有数中连续的最大子段和。
program test7;
var a:array [l..100000] of longint;
n,i,t,ans:longint;
begin
readln (n);
for i:=1 to n do
read(a[i]) ;
t:=a[1];
ans:=t ;
for i:=2 to n do
begin
if t<0 then t:=0
else t:=t+a[i] ;
if t>ans then ans:=t ;
end;
end.