データ構造の最も大きいサブシーケンスの解

転載は出典を明記してください.http://blog.csdn.net/droyon/article/details/8666287
コード量が増えるにつれて、ワークプログラムを書くのに十分ではないことに気づき、プログラムが巨大な数セットで実行されると、プログラムの実行時間が重要な問題になります.まだ符号化されていない場合に、2つのプログラムの実行時間を比較します.およびプログラムの速度を改善し、プログラムの実行のボトルネックを決定し、プログラムをチェックし、パフォーマンスのあるコードセグメントを最適化します.これらはすべてデータ構造が私たちに与えたものです.
アルゴリズム分析:平均実行時間はプログラム実行の典型的な行為に反応し、最悪の実行時間はすべての入力可能な保証を表す.
プログラム効率実行時間計算モデル:
forサイクル:forサイクルメソッド体運転時間 乗算 サイクル数.
ネストforループ:内側のforループ 外のforサイクルを乗じる.
≪順序文｜Order文｜oem_src≫:順序文メソッド・ボディの実行時間の最大値.
if/else文:文時間にメソッド体を加えた最大時間を判断します.
私たちの主役は最も大きなサブシーケンスを解くことと問題です.
最大サブシーケンスの和:一連の数字、任意の連続サブシーケンスの組み合わせ、和を求め、最大和を見つけます.では、次の配列について、最も大きなサブシーケンスを求めて、私たちは何か良い方法がありますか?

int[] values = new int[]{4,-3,5,-2,-1,2,6, -2};

は、4つのアルゴリズムを提供します.
1、:すべてのサブシーケンスを列挙して、最大値を見つけることができます.

public class SubMax1 {
	public static void main(String args[]){
		int[] values = new int[]{4,-3,5,-2,-1,2,6, -2};

		int maxSubCount = maxSub(values);
		System.out.println("       ："+maxSubCount);
	}

	private static int maxSub(int[] array){
		int maxSum=0;
		for(int i=0;i<array.length;i++){
			for(int j=i;j<array.length;j++){
				int sumCount=0;
				for(int k=i;k<j;k++){
					sumCount +=array[k];
				}
				if(sumCount >maxSum){
					maxSum = sumCount;
				}
			}
		}
		return maxSum;
	}
}

実行結果:

     ：11

このアルゴリズムは、すべてのサブシーケンスの可能性をリストし、サブシーケンスの最大値を計算する.この最大値は私たちが求めていることです.
時間解析:三層forサイクルネストを用いたため,時間複雑度はO(Nの三次方)であった.
2、:上の3層のforサイクルがネストされており、1層が過剰に設計されているため、1層のforサイクルを最適化することができます.

public class SubMax2 {
	public static void main(String args[]){
		int[] values = new int[]{4,-3,5,-2,-1,2,6, -2};
		
		int maxSubCount = maxSub(values);
		System.out.println("       ："+maxSubCount);
	}
	private static int maxSub(int[] array){
		int maxSum=0;
		for(int i=0;i<array.length;i++){
			int sumCount=0;
			for(int j=i;j<array.length;j++){
				sumCount +=array[j];
				if(sumCount >maxSum){
					maxSum = sumCount;
				}
			}
		}
		return maxSum;
	}
	
}

実行結果:

     ：11

同様にすべてのサブシーケンスをリストし,サブシーケンスの和を計算したが,このアルゴリズムの時間的複雑度はO(Nの二次方程式)であった.
3、分治法.
問題を2つのほぼ等しいサブ問題に分けて,それらを再帰的に分解する.これは分です.
2つの問題の解を一緒に修正し,最後に最終的な答えを得た.これは治です.
最大サブシーケンスの和は3つに現れる可能性があります.あるいは、入力データの左半歩、または入力データの右半歩、または左半歩と右半歩にまたがるサブシーケンスに現れる.前の2つのケースは再帰的に解くことができ,第3のケースは前の半分(前の半分を含む最後の要素)の最大と加算を求めることができる. 後半(最初の要素を含む)の最大和が得られます. 最後に,左半分,3番目のケースの値,右半分の3つの値の最大値を比較して求めた.

public class SubMax3 {
	public static void main(String args[]){
		int[] values = new int[]{4,-3,5,-2,-1,2,6, -2};
		
		int maxSubCount = maxSub(values, 0, values.length-1);
		System.out.println(maxSubCount+"--------------------");
	}
	public static int maxSub(int[] array,int left,int right){
		int max = 0;
		int leftCount=0;
		int rightCount = 0;
		int leftMaxCountSum=0;
		int rightMaxCountSum = 0;
		
		if(left == right){//           ，    
			if(array[left]>0)return array[left];
			return 0;
		}
		
		int center = (left+right)/2;
		int maxLeftCount = maxSub(array, left, center);
		int maxRightCount = maxSub(array, center+1, right);
		for(int i=center;i>=left;i--){
			leftCount +=array[i];
			if(leftCount>leftMaxCountSum){
				leftMaxCountSum = leftCount;
			}
		}
		
		for(int i = center+1;i<right;i++){
			rightCount += array[i];
			if(rightCount>rightMaxCountSum){
				rightMaxCountSum = rightCount;
			}
		}
		max = returnMax(maxLeftCount, maxRightCount, leftMaxCountSum+ rightMaxCountSum);
		
		return max;
	}
	public static int returnMax(int left,int right,int left_right){
		int max = 0;
		if(left>right){
			max = left;
		}else{
			max = right;
		}
		
		if(max >left_right){
			return max;
		}else{
			return left_right;
		}
	}
	
}

は再帰を使用し、再帰には基準シナリオが必要です.再帰も循環です.このアルゴリズムの時間的複雑度はO(Nlogn)である.
4、時間複雑度O(N)

public class SubMax4 {
	public static void main(String args[]){
		int[] values = new int[]{4,-3,5,-2,-1,2,6, -2};
		int maxSub = maxSub(values);
		System.out.println("     ："+maxSub);
	}
	private static int maxSub(int[] array){
		int maxCount = 0;
		int maxSub = 0;
		for(int i=0;i<array.length;i++){
			maxSub += array[i];
			if(maxSub>maxCount){
				maxCount = maxSub;
			}else if(maxSub<0){
				maxSub = 0;
			}
		}
		return maxCount;
	}
}

このアルゴリズムはプログラミング技術を十分に体現している.
思想:アルゴリズム1とアルゴリズム2のように,iはプログラムの起点を表し,jはプログラムの終点を表す.
a[i]が負の場合、a[i]を起点とする最も大きなサブシーケンスは、a[i+1]を起点として改善できるため、最も大きなサブシーケンスとなる起点は不可能である.
同様に、任意の負のサブシーケンスが最適なサブシーケンスのプレフィックスであることは不可能である.
サブシーケンスa[i]からa[j]において、iからjのサブシーケンスが負であることが検出された場合、iをj+1に進めることができる.pがi+1~jの間であると仮定すると、p~jから始まる任意のサブシーケンスは、i~p−1のサブシーケンスが負ではないので、以下の表i~p−1の任意のサブシーケンスよりも大きくない.すなわち,jはiからjというサブシーケンスが負の値になり始めた最初の下付きスケールであるため,下付きスケールiをj+1に推進することは安全であり,従って最適解を逃すことはない.
利点:このアルゴリズムはデータを1回だけスキャンし、データa[i]が読み込まれて処理されると、保存する必要がなくなります.
また,このアルゴリズムは,プログラムが読み込まれた任意の時点で,最も大きなサブシーケンス問題の正解を与えることができる.このような特性を備えたアルゴリズムをオンラインアルゴリズムと呼ぶ.