1.背景
最大序列和问题一直以来是一个比较经典的算法题，看到这个问题，有很多解题的办法。今天看到了一种时间复杂度只为O(n)的解题算法，在这里记录下。
思路很简单，比方说有P1,P2,P3,P4.....这样一个序列，我们从P1开始求和，比如说在P5时求和数小于零，就可以断定。第一种情况，最大序列在P1~P5之间，或者说在P6~Pn之间。因为如果P1+P2+......+P5的和小于零，那么它可以看成一个数，而且是序列第一个数，则任何一个最大序列都不会包含这个数。
2.代码实现
package Algorithm_analysis;
public class MaxSumOfArray {
public static void main(String args[]){
System.out.print(max_sum());
}
public static int max_sum(){
int[] array={-2,11,-4,13,-5,-2};
int max_sum=0;
int array_sum=0;
for(int j=0;j<array.length;j++)
{
array_sum+=array[j];
if(array_sum<0){
max_sum=0;
}
if (array_sum>max_sum)
{
max_sum=array_sum;
}
}
return max_sum;
}
}
参考：
http://blog.csdn.net/superchanon/article/details/8228212 （完全四种实现方法）
/********************************
* 本文来自博客 “李博Garvin“
* 转载请标明出处:http://blog.csdn.net/buptgshengod
******************************************/
