最長のBitonicサブシーケンス

シーケンスが最初に増加し、次に減少する場合、シーケンスはバイトニックであると言われます。この問題では、すべての正の整数の配列が与えられます。最初に増加し、次に減少するサブシーケンスを見つける必要があります。

この問題を解決するために、2つのサブシーケンスを定義します。これらは、最長増加サブシーケンスと最長減少サブシーケンスです。 LIS配列は、array[i]で終わる増加するサブシーケンスの長さを保持します。 LDS配列は、array[i]から始まる減少するサブシーケンスの長さを格納します。これらの2つの配列を使用して、最長のバイトニックサブシーケンスの長さを取得できます。

入力と出力

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