最長増分サブシーケンスの動的計画の解二(二分ルックアップ最適化)
1638 ワード
1.問題説明:最長増分子シーケンスの長さを解く
入力:最初の行は配列の長さを入力します.
2行目は配列内の要素を入力し始めます
出力:最長増分子シーケンスの長さ
入力4 2 3 1 5 6
出力4(2 3 5 6が最長増分子シーケンスを構成するため)
2.以前、動的計画を用いて解決した構想は、dp[i]は長さiの最長増分サブシーケンスの末尾の数を表し、解く過程で、dp配列の中でarr[i]より大きい最初の下標を見つける必要がある.dp配列の要素はいずれも増加しているため、二分検索の方法を用いて時間の複雑さを低減することができる.
3.最適化後の時間的複雑度はO(nlgn)であり、具体的なコードは以下の通りである.
入力:最初の行は配列の長さを入力します.
2行目は配列内の要素を入力し始めます
出力:最長増分子シーケンスの長さ
入力4 2 3 1 5 6
出力4(2 3 5 6が最長増分子シーケンスを構成するため)
2.以前、動的計画を用いて解決した構想は、dp[i]は長さiの最長増分サブシーケンスの末尾の数を表し、解く過程で、dp配列の中でarr[i]より大きい最初の下標を見つける必要がある.dp配列の要素はいずれも増加しているため、二分検索の方法を用いて時間の複雑さを低減することができる.
3.最適化後の時間的複雑度はO(nlgn)であり、具体的なコードは以下の通りである.
import java.util.Scanner;
public class Main{
// 10 4 2 3 1 5 6 4 8 5 9
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int arr[] = new int[n];
for(int i = 0; i < n; i++){
arr[i] = sc.nextInt();
}
System.out.println(solution(arr));
sc.close();
}
private static int solution(int[] arr){
int dp[] = new int[arr.length + 1];
dp[1] = arr[0];
int p = 1;
for(int i = 1; i < arr.length; i++){
if(arr[i] > dp[p]){
dp[++p] = arr[i];
}else{
// arr[i]
int index = indexOfFirstBigger(0, p, dp, arr[i]);
//
dp[index] = arr[i];
}
}
return p;
}
//
private static int indexOfFirstBigger(int low, int high, int dp[], int k){
if(low >= high) return low;
int mid = (low + high) >> 1;
int midVal = dp[mid];
if(low < high && midVal <= k){
return indexOfFirstBigger(mid + 1, high, dp, k);
}else{
return indexOfFirstBigger(low, mid, dp, k);
}
}
}