C++ 代码

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

const int N = 1e5 + 10;  // 最大数组长度
int n;
int h[N], minh[N];

int main() {
    while (cin >> n) {
        for (int i = 0; i < n; i++) {
            cin >> h[i];  // 读取输入的数组
        }

        int res = 1;
        minh[0] = h[0];  // 初始化第一个元素

        for (int i = 1; i < n; i++) {
            // 使用二分查找来找到 h[i] 应插入的位置
            int low = 0, high = res - 1;
            while (low <= high) {
                int mid = (low + high) / 2;
                if (minh[mid] < h[i]) {
                    low = mid + 1;
                } else {
                    high = mid - 1;
                }
            }

            // low 位置应该是第一个大于等于 h[i] 的地方
            minh[low] = h[i];

            // 如果 low == res，表示需要增加一个新元素
            if (low == res) {
                res++;
            }
        }

        cout << res << endl;  // 输出最长非递减子序列的长度
    }

    return 0;
}