দীর্ঘতম বিটোনিক অনুবর্তন

একটি ক্রমকে বাইটোনিক বলা হয় যদি এটি প্রথমে বৃদ্ধি পায় এবং তারপরে হ্রাস পায়। এই সমস্যায়, সমস্ত ধনাত্মক পূর্ণসংখ্যার একটি অ্যারে দেওয়া হয়। আমাদের এমন একটি অনুবর্তন খুঁজে বের করতে হবে যা প্রথমে বাড়ছে তারপর কমছে।

এই সমস্যাটি সমাধান করার জন্য, আমরা দুটি অনুগামী সংজ্ঞায়িত করব, সেগুলি হল দীর্ঘতম ক্রমবর্ধমান পরবর্তী এবং দীর্ঘতম ক্রমবর্ধমান অনুসূচী। LIS অ্যারে অ্যারে[i] দিয়ে শেষ হওয়া পরবর্তী ক্রমবর্ধমান দৈর্ঘ্য ধরে রাখবে। এলডিএস অ্যারে অ্যারে[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