题目分析 > 模拟 你可以建一个数组 aaa，与一个指针 jjj，初始的时候 j=0j = 0j=0，表示下一个元素存储的位置，也表示 aaa 目前存储的长度，每加入一个元素时将 j+1j + 1j+1。 我们要对输入进来的 nnn 个数 xix_ixi ，判断 xix_ixi 是否允许被加入到 aaa 中。 如果 aaa 此时没有存储任何的数(即 j=0j = 0j=0)，就将 xix_ixi 加入到这个数组中，否则看 xix_ixi 是否大于 aaa 中的最后一个数，即 xi>aj−1x_i \gt a_{j-1}xi >aj−1 ，如果是，则将 xix_ixi 加入到数组中。 最终的答案即为 jjj。 AC代码 复杂度分析 O(n)O(n)O(n)

#include<iostream> using namespace std; int main(){ int m = 1,n; int a[1000000],b[1000000]; cin>>n; for(int i = 1;i <= n;i++){ cin>>b[i]; } a[1] = b[1]; for(int i = 2;i <= n;i++){ if(b[i] > a[m]){ a[m+1] = b[i]; m += 1; } } cout<<m; return 0; }

按题意模拟