最长的双子序列
如果一个序列先增加然后减少，则称其为双子序列。在这个问题中，给出了所有正整数的数组。我们必须找到一个先增大然后减小的子序列。
为了解决这个问题，我们将定义两个子序列，它们是最长增加子序列和最长减少子序列。LIS数组将保留以array[i]结尾的递增子序列的长度。LDS数组将存储从array[i]开始的递减子序列的长度。使用这两个数组，我们可以获得最长的双子序列的长度。
输入输出
Input:
A sequence of numbers. {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15}
Output:
The longest bitonic subsequence length. Here it is 7.算法
longBitonicSub(array, size)
输入：数组，数组的大小。
输出-最长双子序列的最大长度。
Begin
define incSubSeq of size same as the array size
initially fill all entries to 1 for incSubSeq
for i := 1 to size -1, do
for j := 0 to i-1, do
if array[i] > array[j] and incSubSeq[i] < incSubSum[j] + 1, then incSubSum[i] := incSubSum[j] + 1
done
done
define decSubSeq of size same as the array size.
initially fill all entries to 1 for incSubSeq
for i := size - 2 down to 0, do
for j := size - 1 down to i+1, do
if array[i] > array[j] and decSubSeq[i] < decSubSum[j] + 1, then decSubSeq [i] := decSubSeq [j] + 1
done
done
max := incSubSeq[0] + decSubSeq[0] – 1
for i := 1 to size, do
if incSubSeq[i] + decSubSeq[i] – 1 > max, then max := incSubSeq[i] + decSubSeq[i] – 1
done
return max
End示例
#include<iostream>
using namespace std;
int longBitonicSub( int arr[], int size ) {
int *increasingSubSeq = new int[size]; //create increasing sub sequence array
for (int i = 0; i < size; i++)
increasingSubSeq[i] = 1; //set all values to 1
for (int i = 1; i < size; i++) //compute values from left ot right
for (int j = 0; j < i; j++)
if (arr[i] > arr[j] && increasingSubSeq[i] < increasingSubSeq[j] + 1)
increasingSubSeq[i] = increasingSubSeq[j] + 1;
int *decreasingSubSeq = new int [size]; //create decreasing sub sequence array
for (int i = 0; i < size; i++)
decreasingSubSeq[i] = 1; //set all values to 1
for (int i = size-2; i >= 0; i--) //compute values from left ot right
for (int j = size-1; j > i; j--)
if (arr[i] > arr[j] && decreasingSubSeq[i] < decreasingSubSeq[j] + 1)
decreasingSubSeq[i] = decreasingSubSeq[j] + 1;
int max = increasingSubSeq[0] + decreasingSubSeq[0] - 1;
for (int i = 1; i < size; i++) //find max length
if (increasingSubSeq[i] + decreasingSubSeq[i] - 1 > max)
max = increasingSubSeq[i] + decreasingSubSeq[i] - 1;
return max;
}
int main() {
int arr[] = {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15};
int n = 16;
cout << "Length of longest bitonic subsequence is " << longBitonicSub(arr, n);
}输出结果
Length of longest bitonic subsequence is 7