给出一个长度为n 的整数序列A，找出i,j 使得那一段连续数之和最大。第一行为n第二行为数列输入样例63 -5 2 4 -1 6输出样例11希望各位高手帮助，谢谢。

呵呵，好帖，好好看看，

给你点思路。。。定义一个sum，从数列开头向数列尾累加，每累加一个判断如果是整数就记录最大值，如果是sum为负数就将sum归0。这样可以用O(n)的算法求出最大连续子序列了

楼上算法很不错，完善下就是个好程序，

3楼，如果要是 -1 -1 -1 -1 -1 全是负数……我觉得应该回溯

不错，说得好，大家鼓掌

如果有负数，那就分治。分成2段，只要算出左边的最大连续序列，和右边的最大连续序列，还有横跨左右两边的序列就可。递规实现就行，时间复杂度是O(NlogN)

能发这么好的帖子，太谢谢了

不知道是你表达差还是我理解差...这样不是默认了I=1么?

3搂,你这样只从I=1开始加,全部试遍不是很繁么?5楼的同志,说说你的思路

5楼，7楼，如果全是负数，不取最大，不需要分治，3楼的没错啊！9楼，10楼，一开始I=1，可是在程序运行中I是会变得，每次归零时，I都在变化。10楼啊，3楼算法是线性算法啊，O(N)的啊，这样都繁，你还能更简？连数据都不读入就完成了？你也太厉害了！

恩......3楼是标准解法.至于10楼的说3楼的算法繁了,我就有点不理解了.已经是线形时间的算法了,估计也没法优化了.当然,如果你还能想出时间复杂度为O(log n)的算法,我绝对洗耳恭听.下面是我写的代码:program Longest;var a:array[1..1000] of integer; best,sum,n,i:integer;begin ReadLn(n); for i:=1 to n do Read(a[i]); sum:=0; best:=0; for i:=1 to n do if sum+a[i]>0 then begin Inc(sum,a[i]); if sum>best then best:=sum; end else sum:=0; WriteLn(best);end.

int max_sub2(int a[], int size){ int i,max=0,temp_sum=0; for(i=0;i
max) max=temp_sum; else if(temp_sum<0) temp_sum=0; } return max;}在这一遍扫描数组当中，从左到右记录当前子序列的和temp_sum，若这个和不断增加，那么最大子序列的和max也不断增加(不断更新max)。如果往前扫描中遇到负数，那么当前子序列的和将会减小。此时temp_sum 将会小于max，当然max也就不更新。如果temp_sum降到0时，说明前面已经扫描的那一段就可以抛弃了，这时将temp_sum置为0。然后，temp_sum将从后面开始将这个子段进行分析，若有比当前max大的子段，继续更新max。这样一趟扫描结果也就出来了。

经典例题啊,还有一个 最大连续子序列 的变式题.有一N*M的矩阵,试求出最大子矩阵的和INPUT第一行输入N,M下面N行,每行M个数OUTPUT一个数,就是最大子矩阵的和例:INPUT3 41 2 3 45 6 7 89 10 11 -1000OUTPUT54这题有点意思,不要用太多循环,会超时哦.(提示:核心算法可以直接用 最大连续子序列的和 的算法)答案可以到我的Q-ZONE里看http://101064922.qzone.qq.com[OI题解]最大和的子矩阵

可是如果最大值是个负数怎么办？13楼的算法如果最大值是负数，输出来的可是0啊

此时0不就是最大的吗
一个不取，0个元素的子序列反而是和最大的

o（n）的算法
program t1(input,output);{连续最大和}
var
   no:array[1..1000] of longint;
   n,best:longint;
{====================================}
procedure init;
var
   i:longint;
begin
   best:=-maxlongint;
   assign(input,'t1.in');
   assign(output,'t1.out');
   reset(input);
   rewrite(output);
   readln(n);
   for i:=1 to n do read(no[i]);
   close(input);
end;
{====================================}
procedure solve;
var
   i,temp:longint;
begin
   temp:=0;
   for i:=1 to n do
     begin
       inc(temp,no[i]);
       if temp>best then best:=temp;
       if temp<0 then temp:=0;
     end;
   writeln(best);
   close(output);
end;
{====================================}
begin
   init;
   solve;
end.                          
具体见
http://hi.baidu.com/guopiisgood/blog/item/8d0a2b24aa16bd30c995590a.html

DP~~~