最長増加サブシーケンス (LIS)

配列が与えられた場合 到着[] サイズの N 、タスクは、最長増加サブシーケンス (LIS) の長さを見つけることです。つまり、サブシーケンスの要素が昇順に並べ替えられた最長のサブシーケンスです。

最長の増加サブシーケンス

例:

入力： arr[] = {3, 10, 2, 1, 20}
出力： 3
説明： 最長の増加部分列は 3、10、20 です

入力： arr[] = {50, 3, 10, 7, 40, 80}
出力： 4
説明： 最も長い増加部分列は {3, 7, 40, 80} です。

入力： arr[] = {30, 20, 10}
出力： 1
説明： 最も長く増加する部分列は、{30}、{20}、および (10) です。

入力： arr[] = {10, 20, 35, 80}
出力： 4
説明： 配列全体がソートされます

を使用した最長増加シーケンス再帰 :

入力配列を左から右に走査し、すべての要素 arr[i] で終わる最長増加サブシーケンス (LIS) の長さを見つけるというアイデアです。 arr[i] で見つかった長さを L[i] とします。最後に、すべての L[i] 値の最大値を返します。ここで、L[i] をどのように計算するかという疑問が生じます。このために、再帰を使用します。arr[i] の左側にあるすべての小さな要素を考慮し、左側にあるすべての小さな要素の LIS 値を再帰的に計算し、すべての最大値を取得して、それに 1 を加えます。要素の左側に小さい要素がない場合は、1 を返します。

させて L(i) インデックスで終わる LIS の長さになります私 arr[i] が LIS の最後の要素になるようにします。次に、L(i) は次のように再帰的に書くことができます。
VLCでYouTubeビデオをダウンロード

L(i) = 1 + max(L(j) ) ここで 0
そのような j が存在しない場合、L(i) = 1。
正式には、インデックスで終わる LIS の長さ私、あるインデックスで終わるすべての LIS の長さの最大値より 1 大きくなります。 j そのような ar[j] どこ j 。

上記の漸化式は次の関係に従うことがわかります。 最適な下部構造 財産。

図：

理解を深めるために、以下の図に従ってください。

arr[] = {3, 10, 2, 11} を考えてみましょう。

L(i): 位置「i」で終わるサブ配列の LIS を示します

再帰ツリー
CSSで画像を整列させる

上記のアイデアを実装するには、以下の手順に従ってください。

再帰関数を作成します。
再帰呼び出しごとに、 i = 1 現在の位置に移動し、次の操作を行います。
前のシーケンスが次の位置で終了した場合に、現在の位置で終わる最長の増加するサブシーケンスの可能な長さを見つけます。私。
それに応じて、可能な最大長を更新します。
すべてのインデックスに対してこれを繰り返し、答えを見つけます
以下は再帰的アプローチの実装です。
C++// A Naive C++ recursive implementation // of LIS problem #include using namespace std; // To make use of recursive calls, this // function must return two things: // 1) Length of LIS ending with element // arr[n-1]. // We use max_ending_here for this purpose // 2) Overall maximum as the LIS may end // with an element before arr[n-1] max_ref // is used this purpose. // The value of LIS of full array of size // n is stored in *max_ref which is // our final result int _lis(int arr[], int n, int* max_ref) { // Base case if (n == 1) return 1; // 'max_ending_here' is length of // LIS ending with arr[n-1] int res, max_ending_here = 1; // Recursively get all LIS ending with // arr[0], arr[1] ... arr[n-2]. If // arr[i-1] is smaller than arr[n-1], // and max ending with arr[n-1] needs // to be updated, then update it for (int i = 1; i < n; i++) { res = _lis(arr, i, max_ref); if (arr[i - 1] < arr[n - 1] && res + 1>max_ending_here) max_ending_here = res + 1; } // max_ending_here を // 全体の最大値と比較します。そして、 // 必要に応じて全体の最大値を更新します if (*max_ref< max_ending_here) *max_ref = max_ending_here; // Return length of LIS ending // with arr[n-1] return max_ending_here; } // The wrapper function for _lis() int lis(int arr[], int n) { // The max variable holds the result int max = 1; // The function _lis() stores its // result in max _lis(arr, n, &max); // Returns max return max; } // Driver program to test above function int main() { int arr[] = { 10, 22, 9, 33, 21, 50, 41, 60 }; int n = sizeof(arr) / sizeof(arr[0]); // Function call cout << 'Length of lis is ' << lis(arr, n); return 0; }>C// A Naive C recursive implementation // of LIS problem #include #include // To make use of recursive calls, this // function must return two things: // 1) Length of LIS ending with element arr[n-1]. // We use max_ending_here for this purpose // 2) Overall maximum as the LIS may end with // an element before arr[n-1] max_ref is // used this purpose. // The value of LIS of full array of size n // is stored in *max_ref which is our final result int _lis(int arr[], int n, int* max_ref) { // Base case if (n == 1) return 1; // 'max_ending_here' is length of LIS // ending with arr[n-1] int res, max_ending_here = 1; // Recursively get all LIS ending with arr[0], // arr[1] ... arr[n-2]. If arr[i-1] is smaller // than arr[n-1], and max ending with arr[n-1] // needs to be updated, then update it for (int i = 1; i < n; i++) { res = _lis(arr, i, max_ref); if (arr[i - 1] < arr[n - 1] && res + 1>max_ending_here) max_ending_here = res + 1; } // max_ending_here を全体の最大値と // 比較します。そして、必要に応じて全体の最大値を更新します (*max_ref< max_ending_here) *max_ref = max_ending_here; // Return length of LIS ending with arr[n-1] return max_ending_here; } // The wrapper function for _lis() int lis(int arr[], int n) { // The max variable holds the result int max = 1; // The function _lis() stores its result in max _lis(arr, n, &max); // returns max return max; } // Driver program to test above function int main() { int arr[] = { 10, 22, 9, 33, 21, 50, 41, 60 }; int n = sizeof(arr) / sizeof(arr[0]); // Function call printf('Length of lis is %d', lis(arr, n)); return 0; }>ジャワ// A Naive Java Program for LIS Implementation import java.io.*; import java.util.*; class LIS { // Stores the LIS static int max_ref; // To make use of recursive calls, this function must // return two things: 1) Length of LIS ending with // element arr[n-1]. We use max_ending_here for this // purpose 2) Overall maximum as the LIS may end with an // element before arr[n-1] max_ref is used this purpose. // The value of LIS of full array of size n is stored in // *max_ref which is our final result static int _lis(int arr[], int n) { // Base case if (n == 1) return 1; // 'max_ending_here' is length of LIS ending with // arr[n-1] int res, max_ending_here = 1; // Recursively get all LIS ending with arr[0], // arr[1] ... arr[n-2]. If arr[i-1] is smaller // than arr[n-1], and max ending with arr[n-1] needs // to be updated, then update it for (int i = 1; i < n; i++) { res = _lis(arr, i); if (arr[i - 1] < arr[n - 1] && res + 1>max_ending_here) max_ending_here = res + 1; } // max_ending_here を全体の最大値と比較します。そして // 必要に応じて全体の最大値を更新します if (max_ref< max_ending_here) max_ref = max_ending_here; // Return length of LIS ending with arr[n-1] return max_ending_here; } // The wrapper function for _lis() static int lis(int arr[], int n) { // The max variable holds the result max_ref = 1; // The function _lis() stores its result in max _lis(arr, n); // Returns max return max_ref; } // Driver program to test above functions public static void main(String args[]) { int arr[] = { 10, 22, 9, 33, 21, 50, 41, 60 }; int n = arr.length; // Function call System.out.println('Length of lis is ' + lis(arr, n)); } } // This code is contributed by Rajat Mishra>パイソン# A naive Python implementation of LIS problem # Global variable to store the maximum global maximum # To make use of recursive calls, this function must return # two things: # 1) Length of LIS ending with element arr[n-1]. We use # max_ending_here for this purpose # 2) Overall maximum as the LIS may end with an element # before arr[n-1] max_ref is used this purpose. # The value of LIS of full array of size n is stored in # *max_ref which is our final result def _lis(arr, n): # To allow the access of global variable global maximum # Base Case if n == 1: return 1 # maxEndingHere is the length of LIS ending with arr[n-1] maxEndingHere = 1 # Recursively get all LIS ending with # arr[0], arr[1]..arr[n-2] # If arr[i-1] is smaller than arr[n-1], and # max ending with arr[n-1] needs to be updated, # then update it for i in range(1, n): res = _lis(arr, i) if arr[i-1] < arr[n-1] and res+1>maxEndingHere: maxEndingHere = res + 1 # maxEndingHere を全体の最大値と比較します。そして # 必要に応じて全体の最大値を更新します minimum = max(maximum, maxEndingHere) return maxEndingHere def lis(arr): # グローバル変数へのアクセスを許可する global minimum # arr の長さ n = len(arr) # 最大変数は結果を保持しますminimum = 1 # 関数 _lis() は結果を maximum に保存します _lis(arr, n) return minimum # 上記の関数をテストするドライバープログラム if __name__ == '__main__': arr = [10, 22, 9, 33 , 21, 50, 41, 60] n = len(arr) # 関数呼び出し print('lis の長さは', lis(arr)) # このコードは NIKHIL KUMAR SINGH によって提供されています>C#using System; // A Naive C# Program for LIS Implementation class LIS { // Stores the LIS static int max_ref; // To make use of recursive calls, this function must // return two things: 1) Length of LIS ending with // element arr[n-1]. We use max_ending_here for this // purpose 2) Overall maximum as the LIS may end with an // element before arr[n-1] max_ref is used this purpose. // The value of LIS of full array of size n is stored in // *max_ref which is our final result static int _lis(int[] arr, int n) { // Base case if (n == 1) return 1; // 'max_ending_here' is length of LIS ending with // arr[n-1] int res, max_ending_here = 1; // Recursively get all LIS ending with arr[0], // arr[1] ... arr[n-2]. If arr[i-1] is smaller // than arr[n-1], and max ending with arr[n-1] needs // to be updated, then update it for (int i = 1; i < n; i++) { res = _lis(arr, i); if (arr[i - 1] < arr[n - 1] && res + 1>max_ending_here) max_ending_here = res + 1; } // max_ending_here と全体の最大値を比較し、 // 必要に応じて全体の最大値を更新します if (max_ref< max_ending_here) max_ref = max_ending_here; // Return length of LIS ending with arr[n-1] return max_ending_here; } // The wrapper function for _lis() static int lis(int[] arr, int n) { // The max variable holds the result max_ref = 1; // The function _lis() stores its result in max _lis(arr, n); // Returns max return max_ref; } // Driver program to test above functions public static void Main() { int[] arr = { 10, 22, 9, 33, 21, 50, 41, 60 }; int n = arr.Length; // Function call Console.Write('Length of lis is ' + lis(arr, n) + ' '); } }>JavaScript>>
出力
Length of lis is 5>

時間計算量: O(2ⁿ) 上記の再帰的ツリー図で説明したように、部分問題が重複する場合があるため、この再帰的アプローチの時間計算量は指数関数的になります。
補助スペース: ○(1)。内部スタックスペース以外に値を保存するために外部スペースは使用されません。

を使用した最長増加サブシーケンスメモ化 :

注意して見ると、上記の再帰的解決策も次のとおりであることがわかります。 重複する部分問題 プロパティ、つまり、同じ部分構造が異なる再帰呼び出しパスで何度も解決されます。メモ化アプローチを使用すると、これを回避できます。

各状態は 2 つのパラメーターを使用して一意に識別できることがわかります。

現在のインデックス (LIS の最後のインデックスを示します) および
前のインデックス (前の LIS の終了インデックスを示します。 到着しました 連結されています）。
以下は、上記のアプローチの実装です。
C++// C++ code of memoization approach for LIS #include using namespace std; // To make use of recursive calls, this // function must return two things: // 1) Length of LIS ending with element // arr[n-1]. // We use max_ending_here for this purpose // Overall maximum as the LIS may end with // an element before arr[n-1] max_ref is // used this purpose. // The value of LIS of full array of size // n is stored in *max_ref which is // our final result int f(int idx, int prev_idx, int n, int a[], vector>& dp) { if (idx == n) { 0 を返す; } if (dp[idx][prev_idx + 1] != -1) { return dp[idx][prev_idx + 1]; int notTake = 0 + f(idx + 1, prev_idx, n, a, dp); int take = INT_MIN; if (prev_idx == -1 || a[idx]> a[prev_idx]) { take = 1 + f(idx + 1, idx, n, a, dp); dp[idx][prev_idx + 1] = max(take, notTake); を返します。 // 増加する最長のサブシーケンスの長さを見つける関数 int longestSubsequence(int n, int a[]) { Vector> dp(n + 1, ベクトル (n + 1, -1)); f(0, -1, n, a, dp) を返します。 } // 上記をテストするドライバープログラム function int main() { int a[] = { 3, 10, 2, 1, 20 }; int n = sizeof(a) / sizeof(a[0]); // 関数呼び出し cout<< 'Length of lis is ' << longestSubsequence(n, a); return 0; }>ジャワ// A Memoization Java Program for LIS Implementation import java.lang.*; import java.util.Arrays; class LIS { // To make use of recursive calls, this function must // return two things: 1) Length of LIS ending with // element arr[n-1]. We use max_ending_here for this // purpose 2) Overall maximum as the LIS may end with an // element before arr[n-1] max_ref is used this purpose. // The value of LIS of full array of size n is stored in // *max_ref which is our final result static int f(int idx, int prev_idx, int n, int a[], int[][] dp) { if (idx == n) { return 0; } if (dp[idx][prev_idx + 1] != -1) { return dp[idx][prev_idx + 1]; } int notTake = 0 + f(idx + 1, prev_idx, n, a, dp); int take = Integer.MIN_VALUE; if (prev_idx == -1 || a[idx]>a[prev_idx]) { take = 1 + f(idx + 1, idx, n, a, dp); dp[idx][prev_idx + 1] = Math.max(take, notTake); を返します。 } // _lis() のラッパー関数 static int lis(int arr[], int n) { // 関数 _lis() は結果を max int dp[][] = new int[n + 1][ n + 1]; for (int row[] : dp) Arrays.fill(row, -1); f(0, -1, n, arr, dp) を返します; } // 上記の関数をテストするドライバープログラム public static void main(String args[]) { int a[] = { 3, 10, 2, 1, 20 }; int n = a.length; // 関数呼び出し System.out.println('lis の長さは ' + lis(a, n)); } } // このコードは Sanskar によって提供されました。>>パイソン# A Naive Python recursive implementation # of LIS problem import sys # To make use of recursive calls, this # function must return two things: # 1) Length of LIS ending with element arr[n-1]. # We use max_ending_here for this purpose # 2) Overall maximum as the LIS may end with # an element before arr[n-1] max_ref is # used this purpose. # The value of LIS of full array of size n # is stored in *max_ref which is our final result def f(idx, prev_idx, n, a, dp): if (idx == n): return 0 if (dp[idx][prev_idx + 1] != -1): return dp[idx][prev_idx + 1] notTake = 0 + f(idx + 1, prev_idx, n, a, dp) take = -sys.maxsize - 1 if (prev_idx == -1 or a[idx]>a[prev_idx]): take = 1 + f(idx + 1, idx, n, a, dp) dp[idx][prev_idx + 1] = max(take, notTake) return dp[idx][prev_idx + 1] # 最も長く増加する # サブシーケンスの長さを見つける関数。 def longestSubsequence(n, a): dp = [[-1 for i in range(n + 1)]for j in range(n + 1)] return f(0, -1, n, a, dp) # ドライバー上記の関数をテストするプログラム if __name__ == '__main__': a = [3, 10, 2, 1, 20] n = len(a) # 関数呼び出し print('lis の長さは',longestSubsequence( n, a)) # このコードは shinjanpatra によって提供されています>>'C#JavaScript/* A Naive Javascript recursive implementation of LIS problem */ /* To make use of recursive calls, this function must return two things: 1) Length of LIS ending with element arr[n-1]. We use max_ending_here for this purpose 2) Overall maximum as the LIS may end with an element before arr[n-1] max_ref is used this purpose. The value of LIS of full array of size n is stored in *max_ref which is our final result */ function f(idx, prev_idx, n, a, dp) { if (idx == n) { return 0; } if (dp[idx][prev_idx + 1] != -1) { return dp[idx][prev_idx + 1]; } var notTake = 0 + f(idx + 1, prev_idx, n, a, dp); var take = Number.MIN_VALUE; if (prev_idx == -1 || a[idx]>a[prev_idx]) { take = 1 + f(idx + 1, idx, n, a, dp); return (dp[idx][prev_idx + 1] = Math.max(take, notTake)); } // 最も長く増加するサブシーケンスの長さを見つける関数。 // function longestSubsequence(n, a) { var dp = Array(n + 1) .fill() .map(() => Array(n + 1).fill(-1)); f(0, -1, n, a, dp) を返します。 } /* 上記の関数をテストするドライバープログラム */ var a = [3, 10, 2, 1, 20]; var n = 5; console.log('lis の長さは ' +longestSubsequence(n, a)); // このコードは satwiksuman によって寄稿されました。>>
出力
Length of lis is 3>

時間計算量: の上²)
補助スペース: の上²)

を使用した最長増加サブシーケンス動的プログラミング :

最適な部分構造と重複する部分問題の特性により、問題を解決するために動的プログラミングを利用することもできます。メモ化の代わりに、入れ子になったループを使用して再帰的関係を実装できます。

外側のループは次から実行されます。 i = 1 ～ N 内側のループは次から実行されます j = 0 ～ i そして漸化関係を使用して問題を解決します。

上記のアプローチの実装を以下に示します。
ディレクトリ送信とは何ですか
C++// Dynamic Programming C++ implementation // of LIS problem #include using namespace std; // lis() returns the length of the longest // increasing subsequence in arr[] of size n int lis(int arr[], int n) { int lis[n]; lis[0] = 1; // Compute optimized LIS values in // bottom up manner for (int i = 1; i < n; i++) { lis[i] = 1; for (int j = 0; j < i; j++) if (arr[i]>arr[j] && lis[i]< lis[j] + 1) lis[i] = lis[j] + 1; } // Return maximum value in lis[] return *max_element(lis, lis + n); } // Driver program to test above function int main() { int arr[] = { 10, 22, 9, 33, 21, 50, 41, 60 }; int n = sizeof(arr) / sizeof(arr[0]); // Function call printf('Length of lis is %d ', lis(arr, n)); return 0; }>ジャワ// Dynamic Programming Java implementation // of LIS problem import java.lang.*; class LIS { // lis() returns the length of the longest // increasing subsequence in arr[] of size n static int lis(int arr[], int n) { int lis[] = new int[n]; int i, j, max = 0; // Initialize LIS values for all indexes for (i = 0; i < n; i++) lis[i] = 1; // Compute optimized LIS values in // bottom up manner for (i = 1; i < n; i++) for (j = 0; j < i; j++) if (arr[i]>arr[j] && lis[i]< lis[j] + 1) lis[i] = lis[j] + 1; // Pick maximum of all LIS values for (i = 0; i < n; i++) if (max < lis[i]) max = lis[i]; return max; } // Driver code public static void main(String args[]) { int arr[] = { 10, 22, 9, 33, 21, 50, 41, 60 }; int n = arr.length; // Function call System.out.println('Length of lis is ' + lis(arr, n)); } } // This code is contributed by Rajat Mishra>パイソン# Dynamic programming Python implementation # of LIS problem # lis returns length of the longest # increasing subsequence in arr of size n def lis(arr): n = len(arr) # Declare the list (array) for LIS and # initialize LIS values for all indexes lis = [1]*n # Compute optimized LIS values in bottom up manner for i in range(1, n): for j in range(0, i): if arr[i]>arr[j] と lis[i]< lis[j] + 1: lis[i] = lis[j]+1 # Initialize maximum to 0 to get # the maximum of all LIS maximum = 0 # Pick maximum of all LIS values for i in range(n): maximum = max(maximum, lis[i]) return maximum # Driver program to test above function if __name__ == '__main__': arr = [10, 22, 9, 33, 21, 50, 41, 60] print('Length of lis is', lis(arr)) # This code is contributed by Nikhil Kumar Singh>C#// Dynamic Programming C# implementation of LIS problem using System; class LIS { // lis() returns the length of the longest increasing // subsequence in arr[] of size n static int lis(int[] arr, int n) { int[] lis = new int[n]; int i, j, max = 0; // Initialize LIS values for all indexes for (i = 0; i < n; i++) lis[i] = 1; // Compute optimized LIS values in bottom up manner for (i = 1; i < n; i++) for (j = 0; j < i; j++) if (arr[i]>arr[j] && lis[i]< lis[j] + 1) lis[i] = lis[j] + 1; // Pick maximum of all LIS values for (i = 0; i < n; i++) if (max < lis[i]) max = lis[i]; return max; } // Driver code public static void Main() { int[] arr = { 10, 22, 9, 33, 21, 50, 41, 60 }; int n = arr.Length; // Function call Console.WriteLine('Length of lis is ' + lis(arr, n)); } } // This code is contributed by Ryuga>JavaScript>>
出力
Length of lis is 5>

時間計算量: の上²) ネストされたループが使用されるため。
補助スペース: O(N) 各インデックスに LIS 値を格納するために任意の配列を使用します。

注記： 上記の動的プログラミング (DP) ソリューションの時間計算量は O(n^2) ですが、 O(N* logN) 解 LIS問題については。ここでは O(N log N) 解については説明しませんでした。
参照する： 増加する最長サブシーケンスサイズ (N * logN) 前述のアプローチの場合。

を使用した最長増加シーケンス 再帰 :

を使用した最長増加サブシーケンス メモ化 :

を使用した最長増加サブシーケンス 動的プログラミング :

を使用した最長増加シーケンス再帰 :

を使用した最長増加サブシーケンスメモ化 :

を使用した最長増加サブシーケンス動的プログラミング :