Posted on by Kalkicode
Code Array

# Print longest bitonic subarray

The problem involves finding the longest bitonic subarray within a given array of integers. A bitonic subarray is one that first increases in value and then decreases. The problem is to identify and print the longest bitonic subarray in the given array.

## Problem Statement

Given an array of integers, find the longest bitonic subarray and print its elements.

## Example

Consider the following array:

``arr = [1, 2, 3, 2, 4, 5, 6, 3, 2, 1, 2, 3, 4, 3, 9]``

The longest bitonic subarray is `[2, 4, 5, 6, 3, 2, 1]`.

## Idea to Solve

The algorithm involves iterating through the array and identifying bitonic sequences. A bitonic sequence starts with an increasing segment and then transitions to a decreasing segment. The algorithm keeps track of the longest bitonic subarray encountered so far and prints it at the end.

## Pseudocode

``````function bitonic(arr, size):
Initialize variables: stage = 0, x = -1, start = 0, end = 0, length = 0

for i from 0 to size - 2:
Set initial state: stage = 0, x = -1

if arr[i] < arr[i+1]:
Set active stage to 1

for j from i+1 to size - 2:
if stage == 1 and arr[j] > arr[j+1]:
Set stage to 2
else if stage == 2 and arr[j] < arr[j+1]:
Set x = j and break

if stage == 2:
if x == -1:
Set x = size - 1
if (x - i) > length:
Update length, start, and end

if length > 0:
Print elements from start to end
else:
Print "None"``````

## Algorithm Explanation

1. The `bitonic` function iterates through the array and checks for possible bitonic sequences.
2. If an increasing sequence is encountered, the algorithm enters stage 1.
3. If a decreasing sequence is encountered after stage 1, the algorithm enters stage 2 and records the ending index.
4. If stage 2 is entered, the algorithm checks if the bitonic sequence length is greater than the recorded maximum. If so, it updates the length, start, and end variables.
5. Finally, if a valid bitonic sequence is found, the algorithm prints the elements from start to end. If no bitonic sequence is found, it prints "None."

## Code Solution

``````//C Program
//Print longest bitonic subarray
#include<stdio.h>

//Find longest bitonic Sub Array
void bitonic(int arr[],int size)
{
//Variables which are handling execution process
int stage = 0, x = -1, start = 0 ,end =0 ,length = 0;

for (int i = 0; i < size-1; ++i)
{
//Set initial state
stage = 0, x = -1;

//When to adjacency array element [i] is less than [i+1]
//Then there are possible bitonic sequence
if(arr[i] < arr[i+1])
{
//Active state 1
stage=1;

for (int j = i+1; j < size-1; ++j)
{

if(stage == 1 &&  arr[j] > arr[j+1])
{
//When starting the sequence of decrement element
stage = 2;
}
else if(stage == 2 &&  arr[j] < arr[j+1])
{
//bitonic sequence are ends
//get index
x=j;
break;
}

}
//Confirm that the valid bitonic sequence is exist or not
if(stage == 2 )
{
//When valid bitonic sequece exist

if(x == -1)
{
//When the array are last element is part of bitonic
//Sequence then fix the size
x = size-1;
}
if((x-i) > length)
{
//When get new largest bitonic subarray
length = x - i;
start = i;
end = x;
}
}
}
}
if(length > 0)
{
//When exist bitonic sequence
for (int i = start; i <= end; ++i)
{
printf("%3d", arr[i]);
}
}
else
{
//When no bitonic sequence are exist
printf("None\n");
}
}

int main()
{
//Define an array
int arr[] = {1,2,3,2,4,5,6,3,2,1,2,3,4,3,9};
//Get the size
int size = sizeof(arr)/sizeof(arr[0]);

bitonic(arr,size);

return 0;
}``````

#### Output

`` 2  4  5  6  3  2  1``
``````//C++ Program
//Print longest bitonic subarray
#include <iostream>
using namespace std;

class MyArray
{

public:

//Find longest bitonic Sub Array
void bitonic(int arr[],int size)
{
//Variables which are handling execution process
int stage = 0, x = -1, start = 0 ,end =0 ,length = 0;

for (int i = 0; i < size-1; ++i)
{
//Set initial state
stage = 0, x = -1;

//When to adjacency array element [i] is less than [i+1]
//Then there are possible bitonic sequence
if(arr[i] < arr[i+1])
{
//Active state 1
stage=1;

for (int j = i+1; j < size-1; ++j)
{

if(stage == 1 &&  arr[j] > arr[j+1])
{
//When starting the sequence of decrement element
stage = 2;
}
else if(stage == 2 &&  arr[j] < arr[j+1])
{
//bitonic sequence are ends
//get index
x=j;
break;
}

}
//Confirm that the valid bitonic sequence is exist or not
if(stage == 2 )
{
//When valid bitonic sequece exist

if(x == -1)
{
//When the array are last element is part of bitonic
//Sequence then fix the size
x = size-1;
}
if((x-i) > length)
{
//When get new largest bitonic subarray
length = x - i;
start = i;
end = x;
}
}
}
}
if(length > 0)
{
//When exist bitonic sequence
for (int i = start; i <= end; ++i)
{
cout<<"  "<< arr[i];
}
}
else
{
//When no bitonic sequence are exist
cout<<"None"<<endl;
}
}

};

int main()
{

MyArray obj;

//Define an array
int arr[] = {1, 2, 3, 1, 2, 8, 9, 8, 7, 3, 5, 7, 9, 5, 10};
//Get the size
int size = sizeof(arr)/sizeof(arr[0]);

obj.bitonic(arr,size);

return 0;
}``````

#### Output

`` 1  2  8  9  8  7  3``
``````//Java program
//Print longest bitonic subarray
public class MyArray
{

//Find longest bitonic Sub Array
public void  bitonic(int []arr,int size)
{
//Variables which are handling execution process
int stage = 0,
x = -1,
start = 0,
end = 0,
length = 0;

for (int i = 0; i < size-1; ++i)
{
//Set initial state
stage = 0;
x = -1;

//When to adjacency array element [i] is less than [i+1]
//Then there are possible bitonic sequence
if(arr[i] < arr[i+1])
{
//Active state 1
stage=1;

for (int j = i+1; j < size-1; ++j)
{

if(stage == 1 &&  arr[j] > arr[j+1])
{
//When starting the sequence of decrement element
stage = 2;
}
else if(stage == 2 &&  arr[j] < arr[j+1])
{
//bitonic sequence are ends
//get index
x=j;
break;
}

}
//Confirm that the valid bitonic sequence is exist or not
if(stage == 2 )
{
//When valid bitonic sequece exist

if(x == -1)
{
//When the array are last element is part of bitonic
//Sequence then fix the size
x = size-1;
}
if((x-i) > length)
{
//When get new largest bitonic subarray
length = x - i;
start = i;
end = x;
}
}
}
}
if(length > 0)
{
//When exist bitonic sequence
for (int i = start; i <= end; ++i)
{
System.out.print("  "+ arr[i]);
}
}
else
{
//When no bitonic sequence are exist
System.out.println("None");
}
}
public static void main(String[] args)
{
MyArray obj = new MyArray();

//Define an array
int []arr = {1, 2, 3, 1, 2, 8, 9, 8, 7, 3, 5, 7, 9, 5, 10};
//Get the size
int size = arr.length;

obj.bitonic(arr,size);

}
}``````

#### Output

``1  2  8  9  8  7  3``
``````#Python Program
#Print longest bitonic subarray
class MyArray:

#Find longest bitonic Sub Array
def bitonic(self,arr,size) :

#Variables which are handling execution process
stage = 0
x = -1
start = 0
end = 0
length = 0
i = 0
while (i < size-1) :

#Set initial state
stage = 0
x = -1
#When to adjacency array element [i] is less than [i+1]
#Then there are possible bitonic sequence
if(arr[i] < arr[i+1]) :

#Active state 1
stage=1
j = i+1
while ( j < size-1 ) :

if(stage == 1  and   arr[j] > arr[j+1]) :

#When starting the sequence of decrement element
stage = 2
elif(stage == 2  and   arr[j] < arr[j+1]) :

#bitonic sequence are ends
#get index
x=j
break

j+=1
#Confirm that the valid bitonic sequence is exist or not
if(stage == 2 ) :

#When valid bitonic sequece exist
if(x == -1) :

#When the array are last element is part of bitonic
#Sequence then fix the size
x = size-1
if((x-i) > length) :

#When get new largest bitonic subarray
length = x - i
start = i
end = x
i+=1
if(length > 0) :

i = start
#When exist bitonic sequence
while (i <= end) :

print( arr[i], end="  ")
i+=1
else :

#When no bitonic sequence are exist
print("None")

def main():

obj = MyArray()
#Define an array
arr = [1, 2, 3, 1, 2, 8, 9, 8, 7, 3, 5, 7, 9, 5, 10];
#Get the size
size = len(arr);

obj.bitonic(arr,size);

if __name__ =="__main__":
main()``````

#### Output

``1  2  8  9  8  7  3``
``````//C# program
//Print longest bitonic subarray
using System;
public class MyArray
{

//Find longest bitonic Sub Array
public void  bitonic(int []arr,int size)
{
//Variables which are handling execution process
int stage = 0,
x = -1,
start = 0,
end = 0,
length = 0;

for (int i = 0; i < size-1; ++i)
{
//Set initial state
stage = 0;
x = -1;

//When to adjacency array element [i] is less than [i+1]
//Then there are possible bitonic sequence
if(arr[i] < arr[i+1])
{
//Active state 1
stage=1;

for (int j = i+1; j < size-1; ++j)
{

if(stage == 1 &&  arr[j] > arr[j+1])
{
//When starting the sequence of decrement element
stage = 2;
}
else if(stage == 2 &&  arr[j] < arr[j+1])
{
//bitonic sequence are ends
//get index
x=j;
break;
}

}
//Confirm that the valid bitonic sequence is exist or not
if(stage == 2 )
{
//When valid bitonic sequece exist

if(x == -1)
{
//When the array are last element is part of bitonic
//Sequence then fix the size
x = size-1;
}
if((x-i) >length)
{
//When get new largest bitonic subarray
length = x - i;
start = i;
end = x;
}
}
}
}
if(length > 0)
{
//When exist bitonic sequence
for (int i = start; i <= end; ++i)
{
Console.Write("  "+ arr[i]);
}
}
else
{
//When no bitonic sequence are exist
Console.WriteLine("None");
}
}
public static void Main(String[] args)
{
MyArray obj = new MyArray();

//Define an array
int []arr = {1, 2, 3, 1, 2, 8, 9, 8, 7, 3, 5, 7, 9, 5, 10};
//Get the size
int size = arr.Length;

obj.bitonic(arr,size);

}
}``````

#### Output

``````  1  2  8  9  8  7  3
``````
``````<?php
//Php program
//Print longest bitonic subarray

class MyArray
{

//Find longest bitonic Sub Array
function bitonic(\$arr,\$size)
{

//Variables which are handling execution process
\$stage=0;
\$x=-1;
\$start=0;
\$end =0;
\$length=0;

for(\$i=0;  \$i < \$size-1; ++\$i)
{

//Set initial state
\$stage=0;
\$x=-1;

//When to adjacency array element [\$i] is less than [\$i+1]
//Then there are possible bitonic sequence
if ( \$arr[\$i]< \$arr[\$i+1])
{

//Active state 1
\$stage=1;

for(\$j= \$i+1;  \$j< \$size-1; ++\$j)
{

if( \$stage== 1 &&   \$arr[\$j] > (\$arr[\$j+1]))
{
//When starting the sequence of decrement element
\$stage=2;
}
else if( \$stage== 2 &&   \$arr[\$j] < (\$arr[\$j+1]))
{

//bitonic sequence are ends
//get index
\$x= \$j;
break;
}

}

//Confirm that the valid bitonic sequence is exist or not
if ( \$stage== 2)
{

//When valid bitonic sequece exist

if ( \$x== -1)
{

//When the array are last element is part of bitonic
//Sequence then fix the size
\$x= \$size-1;
}
if (( \$x-\$i)> \$length)
{

//When get new largest bitonic subarray
\$length= \$x- \$i;
\$start= \$i;
\$end= \$x;
}
}
}
}
if(\$length>0)
{
//When exist bitonic sequence
for  (\$i= \$start;  \$i<=\$end; ++ \$i)
{
echo  "  ".\$arr[\$i];
}
}
else
{

//When no bitonic sequence are exist
echo  ("None\n");
}
}
}
function main()
{

\$obj= new MyArray();
//Define an array
\$arr = array(1, 2, 3, 1, 2, 8, 9, 8, 7, 3, 5, 7, 9, 5, 10);
//Get the size
\$size = count(\$arr);

\$obj->bitonic(\$arr,\$size);
}
main();
?>``````

#### Output

``1  2  8  9  8  7  3``
``````//Node Js program
//Print longest bitonic subarray
class MyArray {
//Find longest bitonic Sub Array
bitonic(arr, size) {
//Variables which are handling execution process
var stage = 0;
var x = -1;
var start = 0;
var end = 0;
var length = 0;
for (var i = 0; i < size - 1; ++i) {
//Set initial state
stage = 0;
x = -1;
//When to adjacency array element [i] is less than [i+1]
//Then there are possible bitonic sequence

if (arr[i] < arr[i + 1]) {
//Active state 1
stage = 1;
for (var j = i + 1; j < size - 1; ++j) {
if (stage == 1 &&
arr[j] > arr[j + 1]) {
//When starting the sequence of decrement element
stage = 2;
} else
if (stage == 2 &&
arr[j] < arr[j + 1]) {
//bitonic sequence are ends
//get index
x = j;
break;
}
}

//Confirm that the valid bitonic sequence is exist or not

if (stage == 2) {
//When valid bitonic sequece exist

if (x == -1) {
//When the array are last element is part of bitonic
//Sequence then fix the size
x = size - 1;
}

if ((x - i) > length) {
//When get new largest bitonic subarray
length = x - i;
start = i;
end = x;
}
}
}
}

if (length > 0) {
//When exist bitonic sequence

for (var i = start; i <= end; ++i) {
process.stdout.write(" " + arr[i]);
}
} else {
//When no bitonic sequence are exist

process.stdout.write("None");
}
}
}

function main(args) {
var obj = new MyArray();
//Define an array
var arr = [1, 2, 3, 1, 2, 8, 9, 8, 7, 3, 5, 7, 9, 5, 10];
//Get the size
var size = arr.length;
obj.bitonic(arr, size);
}

main();```
```

#### Output

`` 1 2 8 9 8 7 3``
``````# Ruby program
# Print longest bitonic subarray
class MyArray
# Find longest bitonic Sub Array
def bitonic(arr, size)
stage = 0
x = -1
start = 0
last = 0
length = 0
i = 0
while (i < size - 1)
# Set initial state
stage = 0
x = -1
# When to adjacency array element [i] is less than [i+1]
# Then there are possible bitonic sequence

if (arr[i] < arr[i + 1])
# Active state 1
stage = 1
j = i + 1
while (j < size - 1)
if (stage == 1 &&
arr[j] > arr[j + 1])
# When starting the sequence of decrement element
stage = 2
elsif (stage == 2 &&
arr[j] < arr[j + 1])
# bitonic sequence are ends
# get index
x = j
break
end
j += 1
end
# Confirm that the valid bitonic sequence is exist or not

if (stage == 2)
# When valid bitonic sequece exist

if (x == -1)
# When the array are last element is part of bitonic
# Sequence then fix the size
x = size - 1
end
if ((x - i) > length)
# When get new largest bitonic subarray
length = x - i
start = i
last = x
end
end
end
i += 1
end
if (length > 0)
# When exist bitonic sequence
i = start
while (i <= last)
print(" ", arr[i])
i += 1
end
else
print("None")
end
end
end
def main()
obj = MyArray.new()
arr = [1, 2, 3, 1, 2, 8, 9, 8, 7, 3, 5, 7, 9, 5, 10]
size = arr.length
obj.bitonic(arr, size)
end
main()```
```

#### Output

`` 1 2 8 9 8 7 3``
``````//Scala program
//Print longest bitonic subarray
class MyArray {
//Find longest bitonic Sub Array
def bitonic(arr: Array[Int], size: Int): Unit = {
var stage: Int = 0;
var x: Int = -1;
var start: Int = 0;
var last: Int = 0;
var length: Int = 0;
var i: Int = 0;
while (i < size - 1) {
//Set initial state
stage = 0;
x = -1;

//When to adjacency array element [i] is less than [i+1]
//Then there are possible bitonic sequence

if (arr(i) < arr(i + 1)) {
//Active state 1
stage = 1;
var j: Int = i + 1;
while (j < size - 1) {
if (stage == 1 &&
arr(j) > arr(j + 1)) {
//When starting the sequence of decrement element
stage = 2;
} else
if (stage == 2 &&
arr(j) < arr(j + 1)) {
//bitonic sequence are ends
//get index
x = j;
//break the loop
j = size;
}
j += 1;
}
//Confirm that the valid bitonic sequence is exist or not

if (stage == 2) {
//When valid bitonic sequece exist

if (x == -1) {
//When the array are last element is part of bitonic
//Sequence then fix the size
x = size - 1;
}
if ((x - i) > length) {
//When get new largest bitonic subarray
length = x - i;
start = i;
last = x;
}
}
}
i += 1;
}
if (length > 0) {
//When exist bitonic sequence
i = start;
while (i <= last) {
print(" " + arr(i));
i += 1;
}
} else {
print("None");
}
}
}
object Main {
def main(args: Array[String]): Unit = {
var obj: MyArray = new MyArray();
var arr: Array[Int] = Array(1, 2, 3, 1, 2, 8, 9, 8, 7, 3, 5, 7, 9, 5, 10);
var size: Int = arr.length;
obj.bitonic(arr, size);
}
}```
```

#### Output

`` 1 2 8 9 8 7 3``
``````//Swift program
//Print longest bitonic subarray
class MyArray {
//Find longest bitonic Sub Array
func bitonic(_ arr: [Int], _ size: Int) {
var stage: Int = 0;
var x: Int = -1;
var start: Int = 0;
var last: Int = 0;
var length: Int = 0;
var i: Int = 0;
while (i < size - 1) {
//Set initial state
stage = 0;
x = -1;
//When to adjacency array element [i] is less than [i+1]
//Then there are possible bitonic sequence

if (arr[i] < arr[i + 1]) {
//Active state 1
stage = 1;
var j: Int = i + 1;
while (j < size - 1) {
if (stage == 1 &&
arr[j] > arr[j + 1]) {
//When starting the sequence of decrement element
stage = 2;
} else
if (stage == 2 &&
arr[j] < arr[j + 1]) {
//bitonic sequence are ends
//get index
x = j;
break;
}
j += 1;
}
//Confirm that the valid bitonic sequence is exist or not

if (stage == 2) {
//When valid bitonic sequece exist

if (x == -1) {
//When the array are last element is part of bitonic
//Sequence then fix the size
x = size - 1;
}
if ((x - i) > length) {
//When get new largest bitonic subarray
length = x - i;
start = i;
last = x;
}
}
}
i += 1;
}
if (length > 0) {
//When exist bitonic sequence
i = start;
while (i <= last) {
print(" ", arr[i], terminator: "");
i += 1;
}
} else {
print("None", terminator: "");
}
}
}
func main() {
let obj: MyArray = MyArray();
let arr: [Int] = [1, 2, 3, 1, 2, 8, 9, 8, 7, 3, 5, 7, 9, 5, 10];
let size: Int = arr.count;
obj.bitonic(arr, size);
}
main();```
```

#### Output

``  1  2  8  9  8  7  3``

## Time Complexity

The algorithm iterates through the array twice: once for the increasing segment and once for the decreasing segment. Therefore, the time complexity is linear, `O(n)`, where `n` is the size of the array.

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

Categories
Relative Post