原文:
给定一个大小为 n 的数组 arr[] ，任务是打印给定数组中最长的双音素子序列。 注意:如果多个pg电子试玩链接的解决方案退出，则打印任何pg电子试玩链接的解决方案。
示例:
输入: arr[] = {1，1 1，2，10，4，5，2，1} 输出: 1 11 10 5 2 1 解释: 上述数组中所有可能的最长双音素子序列为{1，2，10，4，2，1}、{1，11，10，5，2，1}、{1，2，4，5，2，1}。 因此，打印它们中的任何一个来获得答案。
输入: arr[] = {80，60，30，40，20，10} 输出: 80 60 30 20 10
使用额外空间的动态规划方法:关于解决问题的 2d 动态规划方法，请参考。 时间复杂度:o(n2) 辅助空间: o(n 2 )
空间优化方式:上述方式使用的辅助空间可以通过1dt4动态规划t7】进行优化。按照以下步骤解决问题。
- 创建两个数组 lis[] 和 lds[] ，以在每个 i 第索引处分别存储以元素arr【i】结束的最长递增和递减子序列的长度。
- 一旦计算出来，找到包含最大值lis[i] lds[i]–1的 i 第指数
- 创建 res[] 以按元素降序存储最长双音素序列的所有元素，然后按元素升序存储。
- 打印 res[] 数组。
下面是实施上述方法:
c
// c program to implement
// the above approach
#include
using namespace std;
// function to print the longest
// bitonic subsequence
void printres(vector& res)
{
int n = res.size();
for (int i = 0; i < n; i ) {
cout << res[i] << " ";
}
}
// function to generate the longest
// bitonic subsequence
void printlbs(int arr[], int n)
{
// store the lengths of lis
// ending at every index
int lis[n];
// store the lengths of lds
// ending at every index
int lds[n];
for (int i = 0; i < n; i ) {
lis[i] = lds[i] = 1;
}
// compute lis for all indices
for (int i = 0; i < n; i ) {
for (int j = 0; j < i; j ) {
if (arr[j] < arr[i]) {
if (lis[i] < lis[j] 1)
lis[i] = lis[j] 1;
}
}
}
// compute lds for all indices
for (int i = n - 1; i >= 0; i--) {
for (int j = n - 1; j > i; j--) {
if (arr[j] < arr[i]) {
if (lds[i] < lds[j] 1)
lds[i] = lds[j] 1;
}
}
}
// find the index having
// maximum value of
// lis[i] lds[i] - 1
int maxval = arr[0], inx = 0;
for (int i = 0; i < n; i ) {
if (maxval < lis[i] lds[i] - 1) {
maxval = lis[i] lds[i] - 1;
inx = i;
}
}
// stores the count of elements in
// increasing order in bitonic subsequence
int ct1 = lis[inx];
vector res;
// store the increasing subsequence
for (int i = inx; i >= 0 && ct1 > 0; i--) {
if (lis[i] == ct1) {
res.push_back(arr[i]);
ct1--;
}
}
// sort the bitonic subsequence
// to arrange smaller elements
// at the beginning
reverse(res.begin(), res.end());
// stores the count of elements in
// decreasing order in bitonic subsequence
int ct2 = lds[inx] - 1;
for (int i = inx; i < n && ct2 > 0; i ) {
if (lds[i] == ct2) {
res.push_back(arr[i]);
ct2--;
}
}
// print the longest
// bitonic sequence
printres(res);
}
// driver code
int main()
{
int arr[] = { 80, 60, 30, 40, 20, 10 };
int n = sizeof(arr) / sizeof(arr[0]);
printlbs(arr, n);
}
java 语言(一种计算机语言，尤用于创建网站)
// java program to implement
// the above approach
import java.util.*;
class gfg {
// function to print the longest
// bitonic subsequence
static void printres(vector res)
{
enumeration enu = res.elements();
while (enu.hasmoreelements())
{
system.out.print(enu.nextelement() " ");
}
}
// function to generate the longest
// bitonic subsequence
static void printlbs(int arr[], int n)
{
// store the lengths of lis
// ending at every index
int lis[] = new int[n];
// store the lengths of lds
// ending at every index
int lds[] = new int[n];
for(int i = 0; i < n; i )
{
lis[i] = lds[i] = 1;
}
// compute lis for all indices
for(int i = 0; i < n; i )
{
for(int j = 0; j < i; j )
{
if (arr[j] < arr[i])
{
if (lis[i] < lis[j] 1)
lis[i] = lis[j] 1;
}
}
}
// compute lds for all indices
for(int i = n - 1; i >= 0; i--)
{
for(int j = n - 1; j > i; j--)
{
if (arr[j] < arr[i])
{
if (lds[i] < lds[j] 1)
lds[i] = lds[j] 1;
}
}
}
// find the index having
// maximum value of
// lis[i] lds[i] - 1
int maxval = arr[0], inx = 0;
for(int i = 0; i < n; i )
{
if (maxval < lis[i] lds[i] - 1)
{
maxval = lis[i] lds[i] - 1;
inx = i;
}
}
// stores the count of elements in
// increasing order in bitonic subsequence
int ct1 = lis[inx];
vector res = new vector();
// store the increasing subsequence
for(int i = inx; i >= 0 && ct1 > 0; i--)
{
if (lis[i] == ct1)
{
res.add(arr[i]);
ct1--;
}
}
// sort the bitonic subsequence
// to arrange smaller elements
// at the beginning
collections.reverse(res);
// stores the count of elements in
// decreasing order in bitonic subsequence
int ct2 = lds[inx] - 1;
for(int i = inx; i < n && ct2 > 0; i )
{
if (lds[i] == ct2)
{
res.add(arr[i]);
ct2--;
}
}
// print the longest
// bitonic sequence
printres(res);
}
// driver code
public static void main(string[] args)
{
int arr[] = { 80, 60, 30, 40, 20, 10 };
int n = arr.length;
printlbs(arr, n);
}
}
// this code is contributed by chitranayal
python 3
# python3 program to implement
# the above approach
# function to print the longest
# bitonic subsequence
def printres(res):
n = len(res)
for i in range(n):
print(res[i], end = " ")
# function to generate the longest
# bitonic subsequence
def printlbs(arr, n):
# store the lengths of lis
# ending at every index
lis = [0] * n
# store the lengths of lds
# ending at every index
lds = [0] * n
for i in range(n):
lis[i] = lds[i] = 1
# compute lis for all indices
for i in range(n):
for j in range(i):
if arr[j] < arr[i]:
if lis[i] < lis[j] 1:
lis[i] = lis[j] 1
# compute lds for all indices
for i in range(n - 1, -1, -1):
for j in range(n - 1, i, -1):
if arr[j] < arr[i]:
if lds[i] < lds[j] 1:
lds[i] = lds[j] 1
# find the index having
# maximum value of
# lis[i] lds[i] 1
maxval = arr[0]
inx = 0
for i in range(n):
if maxval < lis[i] lds[i] - 1:
maxval = lis[i] lds[i] - 1
inx = i
# stores the count of elements in
# increasing order in bitonic subsequence
ct1 = lis[inx]
res = []
i = inx
# store the increasing subsequence
while i >= 0 and ct1 > 0:
if lis[i] == ct1:
res.append(arr[i])
ct1 -= 1
i -= 1
# sort the bitonic subsequence
# to arrange smaller elements
# at the beginning
res.reverse()
# stores the count of elements in
# decreasing order in bitonic subsequence
ct2 = lds[inx] - 1
i = inx
while i < n and ct2 > 0:
if lds[i] == ct2:
res.append(arr[i])
ct2 -= 1
i = 1
# print the longest
# bitonic sequence
printres(res)
# driver code
arr = [ 80, 60, 30, 40, 20, 10 ]
n = len(arr)
printlbs(arr, n)
# this code is contributed by stuti pathak
c
// c# program to implement
// the above approach
using system;
using system.collections.generic;
class gfg{
// function to print the longest
// bitonic subsequence
static void printres(list res)
{
foreach(int enu in res)
{
console.write(enu " ");
}
}
// function to generate the longest
// bitonic subsequence
static void printlbs(int[] arr, int n)
{
// store the lengths of lis
// ending at every index
int[] lis = new int[n];
// store the lengths of lds
// ending at every index
int[] lds = new int[n];
for (int i = 0; i < n; i )
{
lis[i] = lds[i] = 1;
}
// compute lis for all indices
for (int i = 0; i < n; i )
{
for (int j = 0; j < i; j )
{
if (arr[j] < arr[i])
{
if (lis[i] < lis[j] 1)
lis[i] = lis[j] 1;
}
}
}
// compute lds for all indices
for (int i = n - 1; i >= 0; i--)
{
for (int j = n - 1; j > i; j--)
{
if (arr[j] < arr[i])
{
if (lds[i] < lds[j] 1)
lds[i] = lds[j] 1;
}
}
}
// find the index having
// maximum value of
// lis[i] lds[i] - 1
int maxval = arr[0], inx = 0;
for (int i = 0; i < n; i )
{
if (maxval < lis[i] lds[i] - 1)
{
maxval = lis[i] lds[i] - 1;
inx = i;
}
}
// stores the count of elements in
// increasing order in bitonic subsequence
int ct1 = lis[inx];
list res = new list();
// store the increasing subsequence
for (int i = inx; i >= 0 && ct1 > 0; i--)
{
if (lis[i] == ct1)
{
res.add(arr[i]);
ct1--;
}
}
// sort the bitonic subsequence
// to arrange smaller elements
// at the beginning
res.reverse();
// stores the count of elements in
// decreasing order in bitonic subsequence
int ct2 = lds[inx] - 1;
for (int i = inx; i < n && ct2 > 0; i )
{
if (lds[i] == ct2)
{
res.add(arr[i]);
ct2--;
}
}
// print the longest
// bitonic sequence
printres(res);
}
// driver code
public static void main(string[] args)
{
int[] arr = {80, 60, 30, 40, 20, 10};
int n = arr.length;
printlbs(arr, n);
}
}
// this code is contributed by amit katiyar
java 描述语言
output:
80 60 30 20 10
时间复杂度:o(n2) 辅助空间: o(n)
麻将胡了pg电子网站的版权属于：月萌api www.moonapi.com，转载请注明出处
