华为机试：Redraimen的走法

#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
using namespace std;

// int findmaxlength(vector<int>& nums, int i) {
//     stack<int> s;
//     int ans = 0;
//     s.push(nums[i]);
//     for (int j = i + 1; j < nums.size(); j++) {
//         if (nums[j] > s.top()) {
//             s.push(nums[j]);
//         }
//         else {
//             ans = max(ans, (int)s.size());
//             while (s.top() != nums[i] && s.top() > nums[j]) {
//                 s.pop();
//             }
//             if (s.top() < nums[j]) {
//                 s.push(nums[j]);
//             }
//         }
//     }
//     if (!s.empty()) {
//         ans = max(ans, (int)s.size());
//     }
//     return ans;
// }

int main() {
    int n;
    cin >> n;
    vector<int> nums;
    int temp;
    while (n--) {
        cin >> temp;
        nums.push_back(temp);
    }
    int ans = 0;
    // for (int i = 0; i < nums.size(); i++) {
    //     ans = max(ans, findmaxlength(nums, i));
    // }
    int N = nums.size();
    vector<int> tails;
    vector<int> dp(N, 0);
    for (int i = 0; i < N; i++) {
        auto it = lower_bound(tails.begin(), tails.end(), nums[i]);
        if (it == tails.end()) {
            tails.push_back(nums[i]);
            dp[i] = tails.size();
        } else {
            *it = nums[i];
            dp[i] = it - tails.begin();
        }
        //dp_left[i] = tails.size();
    }
    for (int i = 0; i < N; i++) {
        ans = max(ans, dp[i]);
    }
    cout << ans << endl;
    return 0;
}