【アルゴリズムデータ構造Java実装】時間複雑度O(n)の最大和シーケンス


1.背景
最大シーケンスと問題はずっと古典的なアルゴリズム問題であり,この問題を見ると,多くの解題方法がある.今日,時間的複雑度がO(n)のみの解題アルゴリズムが見られ,ここで記録される.
考え方は簡単です.例えば、P 1、P 2、P 3、P 4があります.このようなシーケンスでは,P 1から和を求める,例えばP 5で和を求める数がゼロ未満であると断定できる.第1の場合、最大シーケンスはP 1~P 5の間、あるいはP 6~Pnの間である.P 1+P 2+......+P 5の和がゼロ未満であれば、1つの数と見なすことができ、シーケンスの最初の数であれば、どの最大シーケンスもこの数を含まない.
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;jmax_sum)
            {
            	max_sum=array_sum;
            }
	      }
		  return max_sum;

}
	  }

参照先:http://blog.csdn.net/superchanon/article/details/8228212(完全な4つの実装方法)
/********************************
*ブログ「李博Garvin」より
*転載は出典を明記してください:http://blog.csdn.net/buptgshengod
******************************************/