সর্বোচ্চ বিটোনিক সাবসিকোয়েন্স

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

এই সমস্যা সমাধান করার জন্য আমরা দুটি সাবসিকোয়েন্স সংজ্ঞায়িত করব: সর্বোচ্চ ক্রমবর্ধমান সাবসিকোয়েন্স (LIS) এবং সর্বোচ্চ ক্রমহ্রাসমান সাবসিকোয়েন্স (LDS)। LIS অ্যারে array[i]-তে শেষ হওয়া ক্রমবর্ধমান সাবসিকোয়েন্সের দৈর্ঘ্য ধারণ করবে। LDS অ্যারে array[i]-থেকে শুরু হওয়া ক্রমহ্রাসমান সাবসিকোয়েন্সের দৈর্ঘ্য সংরক্ষণ করবে। এই দুটি অ্যারে ব্যবহার করে আমরা সর্বোচ্চ বিটোনিক সাবসিকোয়েন্সের দৈর্ঘ্য পেতে পারি।

ইনপুট এবং আউটপুট

ইনপুট: সংখ্যাগুলোর একটি সিকোয়েন্স।
{0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15}

আউটপুট: সর্বোচ্চ বিটোনিক সাবসিকোয়েন্সের দৈর্ঘ্য। এখানে এটি ৭।

অ্যালগরিদম

longBitonicSub(array, size)

ইনপুট: অ্যারে, অ্যারের আকার।
আউটপুট: সর্বোচ্চ বিটোনিক সাবসিকোয়েন্সের দৈর্ঘ্য।

শুরু
  incSubSeq সংজ্ঞায়িত করুন অ্যারের আকারের সমান
  incSubSeq-এর সকল এন্ট্রি ১ দিয়ে পূরণ করুন
  i := 1 থেকে size-1 পর্যন্ত, করুন
    j := 0 থেকে i-1 পর্যন্ত, করুন
      যদি array[i] > array[j] এবং incSubSeq[i] < incSubSeq[j] + 1 হয়, তবে
        incSubSeq[i] := incSubSeq[j] + 1
    শেষ
  শেষ
  decSubSeq সংজ্ঞায়িত করুন অ্যারের আকারের সমান
  decSubSeq-এর সকল এন্ট্রি ১ দিয়ে পূরণ করুন
  i := size-2 থেকে 0 পর্যন্ত নিচের দিকে, করুন
    j := size-1 থেকে i+1 পর্যন্ত নিচের দিকে, করুন
      যদি array[i] > array[j] এবং decSubSeq[i] < decSubSeq[j] + 1 হয়, তবে
        decSubSeq[i] := decSubSeq[j] + 1
    শেষ
  শেষ
  max := incSubSeq[0] + decSubSeq[0] - 1
  i := 1 থেকে size পর্যন্ত, করুন
    যদি incSubSeq[i] + decSubSeq[i] - 1 > max হয়, তবে
      max := incSubSeq[i] + decSubSeq[i] - 1
  শেষ
  max ফেরত দিন
শেষ

উদাহরণ (C++)

#include <iostream>
using namespace std;

int longBitonicSub(int arr[], int size) {
  int *increasingSubSeq = new int[size];
  for (int i = 0; i < size; i++)
    increasingSubSeq[i] = 1;

  for (int i = 1; i < size; i++)
    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];
  for (int i = 0; i < size; i++)
    decreasingSubSeq[i] = 1;

  for (int i = size-2; i >= 0; i--)
    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++)
    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