正经题解｜上升的列表

题目分析

模拟

你可以建一个数组 $a$，与一个指针 $j$，初始的时候 $j = 0$，表示下一个元素存储的位置，也表示 $a$ 目前存储的长度，每加入一个元素时将 $j + 1$。
我们要对输入进来的 $n$ 个数 $x_i$，判断 $x_i$ 是否允许被加入到 $a$ 中。
如果 $a$ 此时没有存储任何的数(即 $j = 0$)，就将 $x_i$ 加入到这个数组中，否则看 $x_i$ 是否大于 $a$ 中的最后一个数，即 $x_i \gt a_{j-1}$，如果是，则将 $x_i$ 加入到数组中。

最终的答案即为 $j$。

AC代码

#include <iostream>
using namespace std;
int a[1010];
int j = 0;
int main() {
    int n;
    cin >> n;
    for(int i=1;i<=n;i++) {
        int x;
        cin >> x;
        if (j == 0 || x > a[j - 1]) {
            a[j] = x;
            j++;
        }
    }
    cout << j << endl;
    return 0;
}

复杂度分析

$O(n)$