Skip to main content

Print longest bitonic subarray

Here given code implementation process.

//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
Last updated on by Kalkicode




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.

New Comment