この授業では、最大部分の配置を実施しましょう.

1.質問

長さnの配列A[0]、A[1]、...、A[n−1]を入力とすると、i~jの要素からなる配列A[i],...,A[j]は部分配列と呼ばれ、A[i,j]と表される.

この問題の目的は

部分配列のすべての要素の和の最大の部分配列を求めることである.

長さ0の部分配列も許可され、要素の和は0と定義されます.
たとえば、次の配列があります.
-2-1 3 5 2-5 0 2面このアレイの最大部分アレイの和は10(3+5+2)である.

2.解決方法

最大部分の配列の要素の和を求めるアルゴリズムは大体4つあります.

完全なナビゲーション、重複除外ナビゲーション、分割、動的計画

1)完全ナビゲーション(BrootForsアルゴリズム)-時間複雑度O(n^3)

これはすべての部分配列を比較することによって最大配列を求めるアルゴリズムである.

MaxSumは最終結果を表し、ThisSumは各部分配列の和を格納する変数を表す.

三重複文を用いてi(0,n)~j(i,n)の部分配列を求める.

int MaxSubarray1(int A[], int N)
{
	int MaxSum, ThisSum; 
	int i, j, k;
	MaxSum = 0;
	for (i = 0; i < n; i++) {
		for (j = i; j < n; j++) {
			ThisSum = 0;
			for (k = i; k <= j; k++)
				ThisSum = ThisSum + A[k];
			MaxSum = max(MaxSum, ThisSum);
		}
	}
	return MaxSum;
}

-時間の複雑さを求める

時間の複雑さはコマンド実行の個数を求めます!
1つのゲートにn個のデータがある場合(1つのゲートに対して定数時間)
したがって三重複文であるためO(nxnxn)=O(n^3)となる.

特性:時間複雑度がO(n^3)であるため、データの数が多ければ多いほど時間が長くなる.

2）重複除外ナビゲーション

これは1番の方法から重複を除去する方法です.

1番の方法の中ですべての部分の配列の元素の和はそれぞれ1つを求めて、だから繰り返し計算するのはとても多いです

例えば、[0,2]の部分配列の和([0]+[1]+[2])を求めても、次の[0,3]の部分配列は、[0]+[1]+[2]の演算を再開しなければならない.
完璧なアルゴリズムは2番のアルゴリズムです.

int MaxSubarray2(int A[], int N)
{
	int MaxSum, ThisSum;
	int i, j;
	MaxSum = 0;
	for (i = 0; i < n; i++) {
		ThisSum = 0;
		for (j = i; j < n; j++) {
			ThisSum = ThisSum + A[j];
			MaxSum = max(MaxSum, ThisSum);
		}
	}
	return MaxSum;
}

-時間の複雑さを求める

二重複文なのでO(n^2)が必要です.(1を参照)
このアルゴリズムのデータ量が大きいほど,時間が長くなる.

3）分割征服法

部分配列の中間値のインデックスはk(任意の数)である.

kより左だと左右だと右だ

では、すべてのローカル配列は、左側に位置するローカル配列、右側に位置するローカル配列、左側と右側に位置するローカル配列の1つである.
ex: 0 1 2 3 k=4 5 6 7 8

たとえば、0～3のローカル配列、5～8のローカル配列、4のローカル配列があります.

これにより,ループ呼び出し(再帰)を用いて,各属する部分配列の和を求めることができる.
(左側の部分配列を中間値に設定し、左側の左、右…を求めます.このように)横切る部分配列は?->左と右の部分を並べて合わせればいい!

-一番大きいのは?(key)

左から右のローカル配列の最大値と、左から右のローカル配列の最大値を比較します.
最大値は、配列全体の最大部分の配列の要素の和になります.
次の画像を表示します.

int MaxSubarray3(int A[], int Left, int Right)
{
	int MaxSum, MaxLeft, MaxRight, MaxCenter;
	int MaxCenterL, MaxCenterR, ThisSum;
	int Center, i;
	if (Left == Right) {
		if (A[Left] > 0) return A[Left];
		else return 0;
	}
	Center = (Left + Right) / 2;
	MaxLeft = MaxSubarray3(A, Left, Center);
	MaxRight = MaxSubarray3(A, Center + 1, Right);
	MaxCenterL = 0;
	ThisSum = 0;
	for (i = Center; i >= Left; i--) {
		ThisSum = ThisSum + A[i];
		MaxCenterL = max(MaxCenterL, ThisSum);
	}
	MaxCenterR = 0;
	ThisSum = 0;
	for (i = Center + 1; i <= Right; i++) {
		ThisSum = ThisSum + A[i];
		MaxCenterR = max(MaxCenterR, ThisSum);
	}
	MaxCenter = MaxCenterL + MaxCenterR;
	MaxSum = max(max(MaxLeft, MaxRight), MaxCenter);
	return MaxSum;
}

まず関数の引数を見てみましょう.
A[]は入力された配列で、左が一番左のインデックス0、右が一番後ろのインデックスn-1になります.
(配列の大きさがnなので、最後尾の配列のインデックスはn-1)
宣言された変数を見てください.
MaxSum=最終部分配列要素の最大値
MaxLeft=左側の部分配列の最大値
Max Right=右側の部分配列の最大値
Max Center=両端のローカル配列の最大値
MaxCenter=左配列の一部配列の最大値
MaxCenter=右配列の一部配列の最大値

(条件文)

if (Left == Right) {
		if (A[Left] > 0) return A[Left];
		else return 0;
	} 
  왼쪽과 오른쪽의 인덱스가 같을 때이다. 즉 배열의 크기가 1일 때 재귀함수가 끝난다.

(中心値(k)LeftとRightの平均値)

Center = (Left + Right) / 2;
	MaxLeft = MaxSubarray3(A, Left, Center);
	MaxRight = MaxSubarray3(A, Center + 1, Right);
	MaxCenterL = 0;
    
 순환 호출을 이용하여 구하려는 배열의 크기가 0이 될 때까지 부분배열을 구한다.
 

(繰り返し)

for (i = Center; i >= Left; i--) {
		ThisSum = ThisSum + A[i];
		MaxCenterL = max(MaxCenterL, ThisSum);
	}
    
i가 center부터 left까지 감소하면서 부분배열의 합을 구한다.

그리고 합을 구하면서 부분배열의 최대값을 구한다.

MaxCenter = MaxCenterL + MaxCenterR;
	MaxSum = max(max(MaxLeft, MaxRight), MaxCenter);
    
    
 걸쳐있는 배열은 left배열에서의 최대값과 right배열에서의 최대값을 더한 값

최종 결과값은 left, right, center에서 가장 큰 값이 최대부분배열의 원소의 합이 된다.   

時間の複雑さを求めます

T(n)がnの配列の中で最大部分の配列を求めるのに要する時間.
n=1の場合(アレイサイズが1の場合)、左右が等しい場合(0の場合)if文が実行されるので、定数時間(O(1)となる.
n>=2の場合,配列を半分に分割し,n/2の配列ごとにループ呼び出しを行う.
どちらのfor文もO(n)時間かかります.
総消費時間T(n)=2*T(n/2)(ループ呼び出し時間)+O(n).

では、数学計算(点計算式)で時間の複雑さを求めましょう.

時間複雑度はO(nlogn)であった.

4.動的計画法（dp）

部分配列右端A[k]の最大部分配列の要素の和をS[k]と呼ぶ

では、最大部分配列要素とは、S[0]、S[1]、...、S［n−1］の1つかもしれない.

               S[k] = max{S[k-1] + A[k], 0}

위 식을 증명해보자

오른쪽 끝이 A[k]인 최대 부분배열의 길이는 0이거나 1이상일 것이다.

길이가 0인 경우,  S[k] = 0

길이가 1이상인 경우, 

S[k]에서 원소 A[k](오른쪽 끝에있는 원소)를 제거하면 오른쪽 끝이 A[k-1]인 최대 부분배열이 된다.  

<コード>

int MaxSubarray4(int A[], int N)
{
	int MaxSum, ThisSum;
	int k;
	MaxSum = 0;
	ThisSum = 0;
	for (k = 0; k < n; k++) {
		ThisSum = max(ThisSum + A[k], 0);
		MaxSum = max(MaxSum, ThisSum);
	}
	return MaxSum;
}

-時間の複雑さを求める

時間的複雑さはO(n)であることが明らかになった.