最長ビットニック サブシーケンス問題は、最初に増加し、次に減少するような、指定されたシーケンスの最長のサブシーケンスを見つけることです。昇順にソートされたシーケンスは、降順部分が空である Bitonic とみなされます。同様に、降順シーケンスは増加部分を空としてビットニックとみなされます。 例:
Input: [1 11 2 10 4 5 2 1] Output: [1 2 10 4 2 1] OR [1 11 10 5 2 1] OR [1 2 4 5 2 1] Input: [12 11 40 5 3 1] Output: [12 11 5 3 1] OR [12 40 5 3 1] Input: [80 60 30 40 20 10] Output: [80 60 30 20 10] OR [80 60 40 20 10]
で 前の この投稿では、最長ビットニック部分列問題について説明しました。ただし、この投稿では、増加するサブシーケンスの最大合計を見つけることに関連するコードのみがカバーされており、サブシーケンスの構築についてはカバーされていません。この記事では、Longest Bitonic Subsequence 自体を構築する方法について説明します。 arr[0..n-1] を入力配列とします。 LIS[i] 自体が、arr[i] で終わる arr[0..i] の最長増加部分列を格納するベクトルであるように、ベクトル LIS を定義します。したがって、インデックス i について LIS[i] は次のように再帰的に書くことができます -
LIS[0] = {arr[O]} LIS[i] = {Max(LIS[j])} + arr[i] where j < i and arr[j] < arr[i] = arr[i] if there is no such j また、LDS[i] 自体が arr[i] で始まる arr[i..n] の最長減少部分列を格納するベクトルとなるようなベクトル LDS を定義します。したがって、インデックス i について、LDS[i] は次のように再帰的に書くことができます -
LDS[n] = {arr[n]} LDS[i] = arr[i] + {Max(LDS[j])} where j > i and arr[j] < arr[i] = arr[i] if there is no such j たとえば、配列 [1 11 2 10 4 5 2 1] の場合
LIS[0]: 1 LIS[1]: 1 11 LIS[2]: 1 2 LIS[3]: 1 2 10 LIS[4]: 1 2 4 LIS[5]: 1 2 4 5 LIS[6]: 1 2 LIS[7]: 1
LDS[0]: 1 LDS[1]: 11 10 5 2 1 LDS[2]: 2 1 LDS[3]: 10 5 2 1 LDS[4]: 4 2 1 LDS[5]: 5 2 1 LDS[6]: 2 1 LDS[7]: 1
したがって、最長ビットニックサブシーケンスは次のようになります。
LIS[1] + LDS[1] = [1 11 10 5 2 1] OR LIS[3] + LDS[3] = [1 2 10 5 2 1] OR LIS[5] + LDS[5] = [1 2 4 5 2 1]
以下は上記のアイデアの実装です –
C++/* Dynamic Programming solution to print Longest Bitonic Subsequence */ #include
/* Dynamic Programming solution to print Longest Bitonic Subsequence */ import java.util.*; class GFG { // Utility function to print Longest Bitonic // Subsequence static void print(Vector<Integer> arr int size) { for (int i = 0; i < size; i++) System.out.print(arr.elementAt(i) + ' '); } // Function to construct and print Longest // Bitonic Subsequence static void printLBS(int[] arr int n) { // LIS[i] stores the length of the longest // increasing subsequence ending with arr[i] @SuppressWarnings('unchecked') Vector<Integer>[] LIS = new Vector[n]; for (int i = 0; i < n; i++) LIS[i] = new Vector<>(); // initialize LIS[0] to arr[0] LIS[0].add(arr[0]); // Compute LIS values from left to right for (int i = 1; i < n; i++) { // for every j less than i for (int j = 0; j < i; j++) { if ((arr[i] > arr[j]) && LIS[j].size() > LIS[i].size()) { for (int k : LIS[j]) if (!LIS[i].contains(k)) LIS[i].add(k); } } LIS[i].add(arr[i]); } /* * LIS[i] now stores Maximum Increasing Subsequence * of arr[0..i] that ends with arr[i] */ // LDS[i] stores the length of the longest // decreasing subsequence starting with arr[i] @SuppressWarnings('unchecked') Vector<Integer>[] LDS = new Vector[n]; for (int i = 0; i < n; i++) LDS[i] = new Vector<>(); // initialize LDS[n-1] to arr[n-1] LDS[n - 1].add(arr[n - 1]); // Compute LDS values from right to left for (int i = n - 2; i >= 0; i--) { // for every j greater than i for (int j = n - 1; j > i; j--) { if (arr[j] < arr[i] && LDS[j].size() > LDS[i].size()) for (int k : LDS[j]) if (!LDS[i].contains(k)) LDS[i].add(k); } LDS[i].add(arr[i]); } // reverse as vector as we're inserting at end for (int i = 0; i < n; i++) Collections.reverse(LDS[i]); /* * LDS[i] now stores Maximum Decreasing Subsequence * of arr[i..n] that starts with arr[i] */ int max = 0; int maxIndex = -1; for (int i = 0; i < n; i++) { // Find maximum value of size of // LIS[i] + size of LDS[i] - 1 if (LIS[i].size() + LDS[i].size() - 1 > max) { max = LIS[i].size() + LDS[i].size() - 1; maxIndex = i; } } // print all but last element of LIS[maxIndex] vector print(LIS[maxIndex] LIS[maxIndex].size() - 1); // print all elements of LDS[maxIndex] vector print(LDS[maxIndex] LDS[maxIndex].size()); } // Driver Code public static void main(String[] args) { int[] arr = { 1 11 2 10 4 5 2 1 }; int n = arr.length; printLBS(arr n); } } // This code is contributed by // sanjeev2552
# Dynamic Programming solution to print Longest # Bitonic Subsequence def _print(arr: list size: int): for i in range(size): print(arr[i] end=' ') # Function to construct and print Longest # Bitonic Subsequence def printLBS(arr: list n: int): # LIS[i] stores the length of the longest # increasing subsequence ending with arr[i] LIS = [0] * n for i in range(n): LIS[i] = [] # initialize LIS[0] to arr[0] LIS[0].append(arr[0]) # Compute LIS values from left to right for i in range(1 n): # for every j less than i for j in range(i): if ((arr[j] < arr[i]) and (len(LIS[j]) > len(LIS[i]))): LIS[i] = LIS[j].copy() LIS[i].append(arr[i]) # LIS[i] now stores Maximum Increasing # Subsequence of arr[0..i] that ends with # arr[i] # LDS[i] stores the length of the longest # decreasing subsequence starting with arr[i] LDS = [0] * n for i in range(n): LDS[i] = [] # initialize LDS[n-1] to arr[n-1] LDS[n - 1].append(arr[n - 1]) # Compute LDS values from right to left for i in range(n - 2 -1 -1): # for every j greater than i for j in range(n - 1 i -1): if ((arr[j] < arr[i]) and (len(LDS[j]) > len(LDS[i]))): LDS[i] = LDS[j].copy() LDS[i].append(arr[i]) # reverse as vector as we're inserting at end for i in range(n): LDS[i] = list(reversed(LDS[i])) # LDS[i] now stores Maximum Decreasing Subsequence # of arr[i..n] that starts with arr[i] max = 0 maxIndex = -1 for i in range(n): # Find maximum value of size of LIS[i] + size # of LDS[i] - 1 if (len(LIS[i]) + len(LDS[i]) - 1 > max): max = len(LIS[i]) + len(LDS[i]) - 1 maxIndex = i # print all but last element of LIS[maxIndex] vector _print(LIS[maxIndex] len(LIS[maxIndex]) - 1) # print all elements of LDS[maxIndex] vector _print(LDS[maxIndex] len(LDS[maxIndex])) # Driver Code if __name__ == '__main__': arr = [1 11 2 10 4 5 2 1] n = len(arr) printLBS(arr n) # This code is contributed by # sanjeev2552
/* Dynamic Programming solution to print longest Bitonic Subsequence */ using System; using System.Linq; using System.Collections.Generic; class GFG { // Utility function to print longest Bitonic // Subsequence static void print(List<int> arr int size) { for (int i = 0; i < size; i++) Console.Write(arr[i] + ' '); } // Function to construct and print longest // Bitonic Subsequence static void printLBS(int[] arr int n) { // LIS[i] stores the length of the longest // increasing subsequence ending with arr[i] List<int>[] LIS = new List<int>[n]; for (int i = 0; i < n; i++) LIS[i] = new List<int>(); // initialize LIS[0] to arr[0] LIS[0].Add(arr[0]); // Compute LIS values from left to right for (int i = 1; i < n; i++) { // for every j less than i for (int j = 0; j < i; j++) { if ((arr[i] > arr[j]) && LIS[j].Count > LIS[i].Count) { foreach (int k in LIS[j]) if (!LIS[i].Contains(k)) LIS[i].Add(k); } } LIS[i].Add(arr[i]); } /* * LIS[i] now stores Maximum Increasing Subsequence * of arr[0..i] that ends with arr[i] */ // LDS[i] stores the length of the longest // decreasing subsequence starting with arr[i] List<int>[] LDS = new List<int>[n]; for (int i = 0; i < n; i++) LDS[i] = new List<int>(); // initialize LDS[n-1] to arr[n-1] LDS[n - 1].Add(arr[n - 1]); // Compute LDS values from right to left for (int i = n - 2; i >= 0; i--) { // for every j greater than i for (int j = n - 1; j > i; j--) { if (arr[j] < arr[i] && LDS[j].Count > LDS[i].Count) foreach (int k in LDS[j]) if (!LDS[i].Contains(k)) LDS[i].Add(k); } LDS[i].Add(arr[i]); } // reverse as vector as we're inserting at end for (int i = 0; i < n; i++) LDS[i].Reverse(); /* * LDS[i] now stores Maximum Decreasing Subsequence * of arr[i..n] that starts with arr[i] */ int max = 0; int maxIndex = -1; for (int i = 0; i < n; i++) { // Find maximum value of size of // LIS[i] + size of LDS[i] - 1 if (LIS[i].Count + LDS[i].Count - 1 > max) { max = LIS[i].Count + LDS[i].Count - 1; maxIndex = i; } } // print all but last element of LIS[maxIndex] vector print(LIS[maxIndex] LIS[maxIndex].Count - 1); // print all elements of LDS[maxIndex] vector print(LDS[maxIndex] LDS[maxIndex].Count); } // Driver Code public static void Main(String[] args) { int[] arr = { 1 11 2 10 4 5 2 1 }; int n = arr.Length; printLBS(arr n); } } // This code is contributed by PrinciRaj1992
// Function to print the longest bitonic subsequence function _print(arr size) { for (let i = 0; i<size; i++) { process.stdout.write(arr[i]+' '); } } // Function to construct and print the longest bitonic subsequence function printLBS(arr n) { // LIS[i] stores the length of the longest increasing subsequence ending with arr[i] let LIS = new Array(n); for (let i = 0; i < n; i++) { LIS[i] = []; } // initialize LIS[0] to arr[0] LIS[0].push(arr[0]); // Compute LIS values from left to right for (let i = 1; i < n; i++) { // for every j less than i for (let j = 0; j < i; j++) { if (arr[j] < arr[i] && LIS[j].length > LIS[i].length) { LIS[i] = LIS[j].slice(); } } LIS[i].push(arr[i]); } // LIS[i] now stores the Maximum Increasing Subsequence of arr[0..i] that ends with arr[i] // LDS[i] stores the length of the longest decreasing subsequence starting with arr[i] let LDS = new Array(n); for (let i = 0; i < n; i++) { LDS[i] = []; } // initialize LDS[n-1] to arr[n-1] LDS[n - 1].push(arr[n - 1]); // Compute LDS values from right to left for (let i = n - 2; i >= 0; i--) { // for every j greater than i for (let j = n - 1; j > i; j--) { if (arr[j] < arr[i] && LDS[j].length > LDS[i].length) { LDS[i] = LDS[j].slice(); } } LDS[i].push(arr[i]); } // reverse the LDS vector as we're inserting at the end for (let i = 0; i < n; i++) { LDS[i].reverse(); } // LDS[i] now stores the Maximum Decreasing Subsequence of arr[i..n] that starts with arr[i] let max = 0; let maxIndex = -1; for (let i = 0; i < n; i++) { // Find maximum value of size of LIS[i] + size of LDS[i] - 1 if (LIS[i].length + LDS[i].length - 1 > max) { max = LIS[i].length + LDS[i].length - 1; maxIndex = i; } } // print all but // print all but last element of LIS[maxIndex] array _print(LIS[maxIndex].slice(0 -1) LIS[maxIndex].length - 1); // print all elements of LDS[maxIndex] array _print(LDS[maxIndex] LDS[maxIndex].length); } // Driver program const arr = [1 11 2 10 4 5 2 1]; const n = arr.length; printLBS(arr n);
出力：
1 11 10 5 2 1
時間計算量 上記の動的計画法ソリューションは O(n2）。 補助スペース プログラムで使用されるのは O(n2）。