最強増分部分数列(LIS)アルゴリズム

最大増分部分数列(LIS)アルゴリズム

最大インクリメンタルカウントとは?

要素個nの個人配列の部分要素では、各要素が前の要素より大きい条件を満たし、その長さが最も大きい部分数列を最長増分部分数列と呼ぶ.
通常LISの簡便な方法としてはDPがある.

for (int k=0; k<n; k++){
	length[k] = 1;
	for (int i=0; i<k; i++){
		if(arr[i] < arr[k]){
			length[k] = max(length[k], length[i] + 1);
		}
	}
}

上記のコードでは、length[I]は、iの最初のインデックスに終了する最長増分部分数列の長さを表す.
更新条件:

iのインデックスが終了する最大増分列の最後にarr[k]が追加されたときのLIS長と

.

を追加せず、既存の長さ[k]値

では、length[k]値をより大きな値で更新する.

しかし,上記アルゴリズムの時間的複雑度はO(n^2)である.壮大さは非効率と言える.

二分ナビゲーションを使用したLIS

LISの形態を維持するために,所与の配列のインデックスを1つずつ表示し,その数値を二分ナビゲーションで入れる.
この探索は一般に時間的複雑度がO(logn)であると考えられるため,O(blog)の時間的複雑度で上記の問題を解決することができる.

int n;
int arr[40001];
int lis[40001];

int binarySearch(int left, int right, int target){
	int mid;
	while(left<right){
		mid = (left+right)/2;
		if(lis[mid] < target){
			left = mid+1;
		}
		else{
			right = mid;
		}
	}
	return right;
}

int main(){
	int n;
	cin >> n;
	for(int i=0; i<n; i++){
		cin >> arr[i];
	}

	int j=0;
	lis[0] = arr[0]
	int i=1;
	while(i<n){
		if(lis[j] < arr[i]){
			lis[j+1] = arr[i];
			j+=1
		}
		else{
			int pos = binarySearch(0,j,arr[i]);
			lis[pos] = arr[i];
		}
		i+=1;
	}
	cout<< j+1;
	return 0;
}

上のコードはLISの長さを求める方法だけです.
実際のLISを手に入れたい場合は、次の方法を使用します.

角数がLIS配列に入ると、いくつ目のインデックスがrecordというリストに保存されます.

以降、レコードがいっぱいになった場合、レコードの最大値から逆順にループし、対応する値をLISResultに格納します.

LISResultを昇順に並べます.

実際のLISが完了しました.

REFERENCE

画像ソース:https://yhwan.tistory.com/21