सबसे लंबा बिटोनिक परिणाम

एक अनुक्रम को बिटोनिक कहा जाता है यदि यह पहले बढ़ रहा है और फिर घट रहा है। इस समस्या में, सभी धनात्मक पूर्णांकों की एक सरणी दी गई है। हमें एक बाद की खोज करनी है जो पहले बढ़ रही है और फिर घट रही है।

इस समस्या को हल करने के लिए, हम दो अनुक्रमों को परिभाषित करेंगे, वे सबसे लंबे समय तक बढ़ते हुए और सबसे लंबे समय तक घटते हुए बाद के हैं। एलआईएस सरणी सरणी [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