（转载请注明出处：http://blog.csdn.net/buptgshengod）
1.题目
给定一个数字序列，其中有正有负，确定最大子序列和。用穷举法最好的结果也是时间复杂度O(n²)。后来看到一个聪明的方法，直接使时间复杂度变为O(n)。
2.解法
（1）穷举法
把所有序列都算出来找到最大的。
/*
最大序列和问题的求解，一组数列有正有负，找出其中加起来最大的连续序列。
以如下序列为例-2，11，-4，13，-5，-2
算法一：穷举法
*/
public class Test {
public static void main(String[] args)
{
int[] list={-2,11,-4,13,-5,-2};
int i,j;
int maxsum=0;
int sum=0;
for(j=0;j<list.length;j++)
{
sum=0;
for(i=j;i<list.length;i++)
{
sum+=list[i];
if(sum>maxsum)
{
maxsum=sum;
}
}
}
System.out.print(maxsum);
}
}
（2）联机算法
联机算法是对读入的数据给出正确答案，每次都判断。
因为最大子序列不可能以一个负数作为起始。同理也不可能以一个负序列做起始。
public class test {
public static void main(String []args)
{
int[] list={-2,11,-4,13,-5,-2};
int i,j;
int maxsum=0;
int sum=0;
for(i=0;i<list.length;i++)
{
sum+=list[i];
if(sum>maxsum)
{
maxsum=sum;
}
else
{
if(sum<0)
sum=0;
}
}
System.out.print(maxsum);
}
}
