Problem 62: Longest Bitonic Subsequence
Problem Statement: Given an array of integers, find the length of the longest bitonic subsequence. A bitonic subsequence first increases then decreases.
Input
The first line contains an integer n. The second line contains n space-separated integers.
Output
Print the length of the longest bitonic subsequence.
Examples
Input:
8
1 11 2 10 4 5 2 1
Output:
6
Solution Explanation
Compute the longest increasing subsequence (LIS) for each position from left and longest decreasing subsequence (LDS) for each position from right. Then, for each index, sum the two values and subtract 1.
Solution in C++
#include
#include
#include
using namespace std;
int main(){
int n;
cin >> n;
vector a(n);
for(int i = 0; i < n; i++)
cin >> a[i];
vector lis(n, 1), lds(n, 1);
for(int i = 0; i < n; i++){
for(int j = 0; j < i; j++){
if(a[j] < a[i])
lis[i] = max(lis[i], lis[j] + 1);
}
}
for(int i = n - 1; i >= 0; i--){
for(int j = i + 1; j < n; j++){
if(a[j] < a[i])
lds[i] = max(lds[i], lds[j] + 1);
}
}
int ans = 0;
for(int i = 0; i < n; i++){
ans = max(ans, lis[i] + lds[i] - 1);
}
cout << ans << "\n";
return 0;
}