【算法数据结构Java实现】时间复杂度为O(n)的最大和序列

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

******************************************/