ลำดับ Bitonic ที่ยาวที่สุด

ซีเควนซ์จะเรียกว่าบิตโทนิก หากมีการเพิ่มขึ้นในครั้งแรกแล้วค่อยลดลง ในปัญหานี้ อาร์เรย์ของจำนวนเต็มบวกทั้งหมดจะได้รับ เราต้องหาลำดับรองที่เพิ่มขึ้นก่อนแล้วค่อยลดลง

ในการแก้ปัญหานี้ เราจะกำหนดลำดับย่อยสองส่วน ได้แก่ ลำดับต่อมาที่ยาวที่สุดและลำดับต่อมาที่ลดลงที่ยาวที่สุด อาร์เรย์ LIS จะเก็บความยาวของการเพิ่มลำดับที่ลงท้ายด้วย array[i] อาร์เรย์ LDS จะเก็บความยาวของลำดับย่อยที่ลดลงโดยเริ่มจากอาร์เรย์[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)

ป้อนข้อมูล :อาร์เรย์ ขนาดของอาร์เรย์

ผลลัพธ์ − ความยาวสูงสุดของลำดับย่อย 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