原文:
最长双调和子序列问题是找到给定序列的最长子序列，使它先增加后减少。按递增顺序排序的序列被认为是双音素的，递减部分为空。类似地，递减顺序被认为是 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]
在帖子中，我们已经讨论了最长双调和子序列问题。然而，这篇文章只涵盖了与求增子序列的最大和有关的代码，而没有涉及子序列的构造。在这篇文章中，我们将讨论如何构造最长的双调和子序列本身。
让 arr[0..n-1]是输入数组。我们定义向量 lis 使得 lis[i]本身是一个存储 arr[0]的最长递增子序列的向量..那以逮捕结束。因此，对于索引 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，使得 lds[i]本身是一个存储 arr[i]的最长递减子序列的向量..那从 arr[i]开始。因此，对于索引 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
using namespace std;
// utility function to print longest bitonic
// subsequence
void print(vector& arr, int size)
{
for(int i = 0; i < size; i )
cout << arr[i] << " ";
}
// function to construct and print longest
// bitonic subsequence
void printlbs(int arr[], int n)
{
// lis[i] stores the length of the longest
// increasing subsequence ending with arr[i]
vector> lis(n);
// initialize lis[0] to arr[0]
lis[0].push_back(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[j] < arr[i]) &&
(lis[j].size() > lis[i].size()))
lis[i] = lis[j];
}
lis[i].push_back(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]
vector> lds(n);
// initialize lds[n-1] to arr[n-1]
lds[n - 1].push_back(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()))
lds[i] = lds[j];
}
lds[i].push_back(arr[i]);
}
// reverse as vector as we're inserting at end
for (int i = 0; i < n; i )
reverse(lds[i].begin(), lds[i].end());
/* 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 program
int main()
{
int arr[] = { 1, 11, 2, 10, 4, 5, 2, 1 };
int n = sizeof(arr) / sizeof(arr[0]);
printlbs(arr, n);
return 0;
}
java 语言(一种计算机语言，尤用于创建网站)
/* dynamic programming solution to print longest
bitonic subsequence */
import java.util.*;
class gfg
{
// utility function to print longest bitonic
// subsequence
static void print(vector 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[] 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[] 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
python 3
# 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
c
/* 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 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[] lis = new list[n];
for (int i = 0; i < n; i )
lis[i] = new list();
// 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[] lds = new list[n];
for (int i = 0; i < n; i )
lds[i] = new list();
// 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
output:
1 11 10 5 2 1
以上动态规划解的时间复杂度为 o(n 2 )。 程序使用的辅助空间为 o(n 2 )。
本文由阿迪蒂亚·戈尔供稿。如果你喜欢 geeksforgeeks 并想投稿，你也可以使用写一篇文章或者把你的文章邮寄到 contribute@geeksforgeeks.org。看到你的文章出现在极客博客pg电子试玩链接主页上，帮助其他极客。
如果你发现任何不正确的地方，或者你想分享更多关于上面讨论的话题的信息，请写评论。
麻将胡了pg电子网站的版权属于：月萌api www.moonapi.com，转载请注明出处
