A **bitonic sequence** is a sequence of numbers in which, at first, the numbers are in increasing order, and after a certain point, they start decreasing.

The sequence

A bitonic subsequence can be of the following three types:

It can consist of numbers that are first increasing and then decreasing. For example,

$(2,6,9,3,2)$ .It can consist of numbers that are only increasing (where the decreasing part at the end is empty). For example,

$(2,3,7,9)$ .It can consist of numbers that are only decreasing (where the increasing part at the start is empty). For example,

$(15,12,5,3,2,1)$ .

Let's implement the code to find if the given sequence is a bitonic sequence.

#include <iostream>using namespace std;// Helper function to print sequencevoid printSequence(int arr[], int n){string out = "[";for (int i = 0; i < n; i++){out+= to_string(arr[i]) + ", ";}out = out.substr(0, out.length() -2);out += "]";cout << out << endl;}// Finding index of maximum value in an arrayint find_maxIndex(int arr[], int n){int max_index = 0;for (int i = 1; i < n; i++){if (arr[i] > arr[max_index]){max_index = i;}}return max_index;}bool isIncreasingBitonic(int arr[], int low, int high){//Base caseif (high == low){return true;}// Checking for the non increasing pair in arrayif (arr[high] < arr[high - 1]){return false;}return isIncreasingBitonic(arr, low, high - 1);}bool isDecreasingBitonic(int arr[], int low, int high){// Base caseif (high == low){return true;}// Checking for the non decreasing in arrayif (arr[high] > arr[high - 1]){return false;}return isDecreasingBitonic(arr, low, high - 1);}bool isBitonic(int arr[], int n, int max_index){// If array is the increasing bitonic// then the maximum element will be at the last indexif(max_index == n){return isIncreasingBitonic(arr,0,n);}// If array is the decreasing bitonic// then the maximum element will be at the 0th indexelse if(max_index == 0){return isDecreasingBitonic(arr,0,n);}// If array is first increasing and then decreasing bitonic// First check for increasing bitonic till max value// Then check for decreasing bitonic from max value till end of arrayelse{return isIncreasingBitonic(arr,0,max_index) && isDecreasingBitonic(arr,max_index,n);}}int main(){int arr[] = {2, 3, 7, 9, 15, 10, 4};int n = sizeof(arr) / sizeof(arr[0]);// Finding index for maximum elementint max_index = find_maxIndex(arr,n);//Printing sequencecout << "The sequence is: ";printSequence(arr, n);// Checking if the array is bitonicif (isBitonic(arr, n-1, max_index)){cout << "This is a bitonic sequence." << endl;}else{cout << "This is not a bitonic sequence." << endl;}return 0;}

**Lines 5–14:**We defined the`printSequence()`

method to print the sequence.**Lines 17–26:**We defined the`find_maxIndex()`

method to find the index of the maximum value in the sequence.**Lines 28–40:**We defined the recursive method`isIncreasingBitonic()`

to find if the array is an increasing bitonic sequence.**Lines 42–54**: We defined the recursive method`isDecreasingBitonic()`

to find if the array is a decreasing bitonic sequence.**Lines 56–73:**We write the`isBitonic()`

method which uses the`isIncreasingBitonic()`

and`isDecreasingBitonic()`

method to find if the given sequence is a bitonic sequence or not.

Copyright ©2024 Educative, Inc. All rights reserved

TRENDING TOPICS