HackerRank

It requires O(nlgn) solution. And actually I think the passing code is for "non-decreasing"..

#include <cmath>
#include <cstdio>
#include <vector>
#include <unordered_set>
#include <string>
#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    int t; cin >> t;
    vector<int> arr(t);
    for (int i = 0; i < t; i++)
        cin >> arr[i];

    vector<int> dp(t, 1);

    //    c[i]: Smallest LAST elem of a LIS seq with lenghth i
    vector<int> c(1, arr[0]);

    int ret = 1;
    for (int i = 1; i < t; i++)
    {
        if (arr[i] <= c[0])
        {
            c[0] = arr[i];
            dp[i] = 1;
        }
        else if (arr[i] >= c.back())
        {
            c.push_back(arr[i]);
            dp[i] = c.size();
        }
        else
        {
            int k = std::lower_bound(c.begin(), c.end(), arr[i]) - c.begin();
            c[k] = arr[i];
            dp[i] = k + 1;
        }
        ret = std::max(ret, dp[i]);
    }
    cout << ret << endl;
    return 0;
}