# Find longest bitonic sequence such that increasing and decreasing parts are from two different arrays

We are given two arrays, we need to find the longest possible bitonic sequence such that increasing part must be from first array and should be a subsequence of first array. Similarly, decreasing part of must be from second array and should be a subsequence of it.

Examples:

```Input : arr1[] = {1, 5, 2, 4, 3, 5},
arr2[] = {8, 6, 4, 7, 3, 2}
Output : 1, 2, 4, 5, 8, 6, 4, 3, 2

Input : arr1[] = {2, 0, 1, 3, 4},
arr2[] = {5, 3, 2, 1}
Output : 0, 1, 2, 3, 4, 5, 3, 2, 1
```

## Recommended: Please try your approach on {IDE} first, before moving on to the solution.

The idea is to use largest increasing sequence from array1 and largest decreasing sequence from array2 and then combine both to get our result.

 `// CPP to find largest bitonic sequence such that ` `#include ` `using` `namespace` `std; ` ` `  `vector<``int``> res; ` ` `  `// utility Binary search ` `int` `GetCeilIndex(``int` `arr[], vector<``int``>& T, ``int` `l,  ` `                                   ``int` `r, ``int` `key) ` `{ ` `    ``while` `(r - l > 1) { ` `        ``int` `m = l + (r - l) / 2; ` `        ``if` `(arr[T[m]] >= key) ` `            ``r = m; ` `        ``else` `            ``l = m; ` `    ``} ` `    ``return` `r; ` `} ` ` `  `// function to find LIS in reverse form ` `void` `LIS(``int` `arr[], ``int` `n) ` `{ ` `    ``// Add boundary case, when array n is zero ` `    ``// Depend on smart pointers ` `    ``vector<``int``> tailIndices(n, 0); ``// Initialized with 0 ` `    ``vector<``int``> prevIndices(n, -1); ``// initialized with -1 ` ` `  `    ``int` `len = 1; ``// it will always point to empty location ` `    ``for` `(``int` `i = 1; i < n; i++) { ` ` `  `        ``// new smallest value ` `        ``if` `(arr[i] < arr[tailIndices[0]])              ` `            ``tailIndices[0] = i; ` ` `  `        ``// arr[i] wants to extend largest subsequence ` `        ``else` `if` `(arr[i] > arr[tailIndices[len - 1]]) {             ` `            ``prevIndices[i] = tailIndices[len - 1]; ` `            ``tailIndices[len++] = i; ` `        ``}  ` `          `  `        ``// arr[i] wants to be a potential candidate of ` `        ``// future subsequence ` `        ``// It will replace ceil value in tailIndices ` `        ``else` `{ ` `            ``int` `pos = GetCeilIndex(arr, tailIndices, -1,  ` `                                        ``len - 1, arr[i]); ` `            ``prevIndices[i] = tailIndices[pos - 1]; ` `            ``tailIndices[pos] = i; ` `        ``} ` `    ``} ` ` `  `    ``// put LIS into vector ` `    ``for` `(``int` `i = tailIndices[len - 1]; i >= 0; i = prevIndices[i]) ` `        ``res.push_back(arr[i]); ` `} ` ` `  `// function for finding longest bitonic seq ` `void` `longestBitonic(``int` `arr1[], ``int` `n1, ``int` `arr2[], ``int` `n2) ` `{ ` `    ``// find LIS of array 1 in reverse form ` `    ``LIS(arr1, n1); ` ` `  `    ``// reverse res to get LIS of first array ` `    ``reverse(res.begin(), res.end()); ` ` `  `    ``// reverse array2 and find its LIS ` `    ``reverse(arr2, arr2 + n2); ` `    ``LIS(arr2, n2); ` ` `  `    ``// print result ` `    ``for` `(``int` `i = 0; i < res.size(); i++) ` `        ``cout << res[i] << ``" "``; ` `} ` ` `  `// driver preogram ` `int` `main() ` `{ ` `    ``int` `arr1[] = { 1, 2, 4, 3, 2 }; ` `    ``int` `arr2[] = { 8, 6, 4, 7, 8, 9 }; ` `    ``int` `n1 = ``sizeof``(arr1) / ``sizeof``(arr1[0]); ` `    ``int` `n2 = ``sizeof``(arr2) / ``sizeof``(arr2[0]); ` `    ``longestBitonic(arr1, n1, arr2, n2); ` `    ``return` `0; ` `} `

Output:

```1 2 3 8 6 4
```

Time Complexity : O(n Log n)
Please note that O(n Log n) implementation of LIS is used

## tags:

Dynamic Programming LIS Dynamic Programming