【アルゴリズムとデータ構造】最大サブシーケンスと問題

(転載は出典を明記してください: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);
   }
}