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;
}