不是VIP会员,不能显示答案

题目解答

题目:
最大子段和
老师给乐乐布置了一份作业, 乐乐不知如何解决,找你帮忙解决。老师给一串很长的数列,要求从中找出连续的一段来使得总和最大。
输入:第一行包括一个整数 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.
考点:
分析:
解答:
评论:
老师: