가장 긴 Bitonic 하위 시퀀스

시퀀스가 처음에는 증가했다가 감소하는 경우 바이토닉(bitonic)이라고 합니다. 이 문제에서는 모든 양의 정수로 구성된 배열이 제공됩니다. 먼저 증가하고 다음 감소하는 부분 수열을 찾아야 합니다.

이 문제를 해결하기 위해 우리는 가장 긴 증가 부분 수열과 가장 긴 감소 부분 수열이라는 두 개의 부분 수열을 정의할 것입니다. LIS 배열은 array[i]로 끝나는 증가하는 부분 시퀀스의 길이를 유지합니다. LDS 배열은 배열[i]에서 시작하여 감소하는 부분 시퀀스의 길이를 저장합니다. 이 두 배열을 사용하여 가장 긴 bitonic 부분 시퀀스의 길이를 얻을 수 있습니다.

입력 및 출력

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)

입력 :배열, 배열의 크기.

출력 - 가장 긴 bitonic 하위 시퀀스의 최대 길이입니다.

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