fork download 
  1. #include<stdio.h> 
  2. #include<stdlib.h> 
  3.  
  4. /* lbs() returns the length of the Longest Bitonic Subsequence in 
  5.     arr[] of size n. The function mainly creates two temporary arrays 
  6.     lis[] and lds[] and returns the maximum lis[i] + lds[i] - 1. 
  7.   
  8.     lis[i] ==> Longest Increasing subsequence ending with arr[i] 
  9.     lds[i] ==> Longest decreasing subsequence starting with arr[i] 
  10. */
  11. int lbs( int arr[], int n ) 
  12. { 
  13.    int i, j; 
  14.  
  15.    /* Allocate memory for LIS[] and initialize LIS values as 1 for 
  16.       all indexes */
  17.    int *lis = new int[n]; 
  18.    for (i = 0; i < n; i++) 
  19.       lis[i] = 1; 
  20.  
  21.    /* Compute LIS values from left to right */
  22.    for (i = 1; i < n; i++) 
  23.       for (j = 0; j < i; j++) 
  24.          if (arr[i] > arr[j] && lis[i] < lis[j] + 1) 
  25.             lis[i] = lis[j] + 1; 
  26.  
  27.    /* Allocate memory for lds and initialize LDS values for 
  28.       all indexes */
  29.    int *lds = new int [n]; 
  30.    for (i = 0; i < n; i++) 
  31.       lds[i] = 1; 
  32.  
  33.    /* Compute LDS values from right to left */
  34.    for (i = n-2; i >= 0; i--) 
  35.       for (j = n-1; j > i; j--) 
  36.          if (arr[i] > arr[j] && lds[i] < lds[j] + 1) 
  37.             lds[i] = lds[j] + 1; 
  38.  
  39.  
  40.    /* Return the maximum value of lis[i] + lds[i] - 1*/
  41.    int max = lis[0] + lds[0] - 1; 
  42.    for (i = 1; i < n; i++) 
  43.      if (lis[i] + lds[i] - 1 > max) 
  44.          max = lis[i] + lds[i] - 1; 
  45.    return max; 
  46. } 
  47.  
  48. /* Driver program to test above function */
  49. int main() 
  50. { 
  51.   int arr[] = {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 
  52.               13, 3, 11, 7, 15}; 
  53.   int n = sizeof(arr)/sizeof(arr[0]); 
  54.   printf("Length of LBS is %d\n", lbs( arr, n ) ); 
  55.   return 0; 
  56. }
Success #stdin #stdout 0s 4508KB
comments (?)
stdin 
Standard input is empty
stdout 
Length of LBS is 7
https://ideone.com/dNE5xK
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!