[UVa]] 10534 - Wavio Sequence

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : 10534 - Wavio Sequence
Source            : UVa Online Judge
Category          : LIS
Algorithm         : LIS
Verdict           : Accepted
#include <bits/stdc++.h>
 
using namespace std;
 
 
static const int MAXN = 1e5 + 5;
 
int arr[MAXN];
vector <int> LIS;
 
int dpLIS[MAXN];
int dpLDS[MAXN];
 
 
int findLIS(int n)
{
    LIS.erase(LIS.begin(), LIS.end());
    vector <int>::iterator it;
    for (int i=1; i <= n; i++)
    {
        it = lower_bound(LIS.begin(), LIS.end(), arr[i]);
        dpLIS[i] = (int)(it - LIS.begin());
        if (it == LIS.end()) LIS.push_back(arr[i]);
        else *it = arr[i];
    }
    LIS.erase(LIS.begin(), LIS.end());
    for (int i = n; i >= 1; i--)
    {
        it = lower_bound(LIS.begin(), LIS.end(), arr[i]);
        dpLDS[i] =  (int) (it - LIS.begin());
        if (it == LIS.end()) LIS.push_back(arr[i]);
        else *it = arr[i];
    }
    int ans = 1;
    for (int i = 1; i <= n; i++)
    {
        int mini = min(dpLIS[i], dpLDS[i]);
        ans = max(mini+mini+1, ans);
    }
    return ans;
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    int n;
    while (cin >> n)
    {
        for (int i = 1; i <= n; i++)
        {
            cin >> arr[i];
        }
        cout << findLIS(n) << endl;
    }
}