[C++]最大サブシーケンスの和を求める4つの方法

33435 ワード
データ構造 C++
に質問
与えられた整数:A 1,A 2,...,An,Σjk=iAkの最大値を求める(便宜上、すべての整数が負の場合、最大サブシーケンスと0)
たとえば
入力:-2,11,-4,13,-5,-2,答えは20,すなわちA 2からA 4まで
ぶんせき
この問題が興味深いのは,それを解くアルゴリズムがたくさんあるからである.
解法一:窮挙遍歴
正直にすべての可能性を挙げて、コードは以下の通りです.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

//             ：    
int maxSubSum1(const vector<int> & a)
{
	//           
	int maxSum = 0;

	//i       
	for (int i = 0; i < a.size(); i++)
	{
		//j       
		for (int j = i; j < a.size(); j++)
		{
			//               
			int thisSum = 0;

			//              
			for (int k = i; k <= j; k++)
			{
				thisSum += a[k];
			}

			//        
			if(thisSum > maxSum)
				maxSum = thisSum;
		}
	}

	return maxSum;
}

これは多くの人が考えている方法です.すべての可能性を列挙し、サブシーケンスのすべての値を加算して和を求めます.簡単に乱暴に問題を解決し、しかもよく理解しています.このアルゴリズムの時間的複雑さはO(N 3)である.
解法二:窮挙最適化
実は3番目のforサイクルはまったく必要ありません.2番目のレイヤforサイクルのときに求めた和を計算し、次のラウンドに持ち込むforサイクルを続ければいいです.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

//             ：    
int maxSubSum2(const vector<int> & a)
{
	//           
	int maxSum = 0;

	//i       
	for (int i = 0; i < a.size(); i++)
	{
		//               
		int thisSum = 0;

		//j       
		for (int j = i; j < a.size(); j++)
		{

			//              
			thisSum += a[j];

			//        
			if(thisSum > maxSum)
				maxSum = thisSum;
		}
	}

	return maxSum;
}

このアルゴリズムの時間的複雑さはO(N 2)である.
解法三:分けて治める
分けて治めるのは,その名の通り二つの部分に分かれている.
分:大きな問題をほぼ等しい2つのサブ問題に分けて,再帰的に解く.
治:二つのサブ問題の解を統合し、少量の付加作業を行う.
最も大きなサブシーケンスの和の問題では、最も大きなサブシーケンスの和が3つの場所に現れる可能性があります.
入力データの左半分に全体が現れる.
入力データ全体の右半分左右の2つの部分にまたがる前の2つについては再帰的に解くことができ,3つ目については左右の2つの部分の和をそれぞれ求め,加算することができる.具体的なコードは以下の通りです.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

//             ：    
int maxSubSum3(const vector<int> & a,int left,int right)
{
	//    ：    。          0
	if(left == right)
	{
		return a[left];
	}

	//    
	int center = (left + right) / 2;

	/*                       */
	int leftMaxSum = maxSubSum3(a,left,center);

	/*                       */
	int rightMaxSum = maxSubSum3(a,center+1,right);

	//                 
	int lrMaxSum = max(leftMaxSum,rightMaxSum);


	/*                  */

	// center       
	int maxLeftSum = 0;
	int leftSum = 0;
	for (int i = center; i >= left; i--)
	{
		leftSum += a[i];
		maxLeftSum = max(maxLeftSum,leftSum);
	}

	// center       
	int maxRightSum = 0;
	int rightSum = 0;
	for (int j = center+1; j <= right; j++)
	{
		rightSum += a[j];
		maxRightSum = max(maxRightSum,rightSum);
	}

	//               
	return max( lrMaxSum, maxLeftSum+maxRightSum);
}

このアルゴリズムの時間的複雑さはO(Nlogn)である.
解法四:オンラインアルゴリズム
まず、オンラインアルゴリズムの概念を説明します.
オンラインアルゴリズム:任意の時点で、アルゴリズムは操作するデータを1回しか読み込まない(スキャン)が、読み込まれて処理されると、記憶される必要はありません.この処理中にアルゴリズムは、読み込まれたデータに対して、対応するサブシーケンス問題の正解を直ちに与えることができる.この特性を有するアルゴリズムをオンラインアルゴリズム(on-line algorithm)と呼ぶ.
この問題について、コードは次のとおりです.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

//             ：    
int maxSubSum4(const vector<int> & a)
{
	//    
	int maxSum = 0;
	//    
	int nowSum = 0;

	//         
	for (int j = 0; j < a.size(); j++)
	{
		//           
		nowSum += a[j];

		//       ，         
		if(nowSum > maxSum)
			maxSum = nowSum;
		else if(nowSum < 0)
			nowSum = 0;
	}

	return maxSum;
}

このアルゴリズムの時間的複雑さはO(N)である.
まとめ
次の表は、統計的な4つのアルゴリズムの演算結果です.
入力サイズ
O(N3)
O(N2)
O(NlogN)
O(N)
N=10
0.000009
0.000004
0.000006
0.000003
N=100
0.002580
0.000109
0.000045
0.000006
N=1000
2.281013
0.010203
0.000485
0.000031
N=10000
NA
1.2329
0.005712
0.000317
N=100000
NA
135
0.064618
0.003206
表から分かるように,データ量が小さい場合(小さい場合=.=),アルゴリズムは瞬時に完成し,差も明らかではない.しかし,入力量が増大するにつれて,いくつかのアルゴリズムの弊害が徐々に現れ,効率が低く,限られた時間でも結果は算出されなかった.多くの効率的なアルゴリズムにとって、データの読み取りは問題を解決するボトルネックになりがちです.
pythonプログラミング:関数を記述し、任意の複数の整数を受信し、その最大値とすべての整数の和を出力します.
COTOHA で固有名詞の抽出 (PHP)