1 int main() 2 { 3 int x; 4 while (cin >> x) 5 a[++n] = x; 6 int len = 1; 7 f[len] = a[1]; 8 for (int i = 2; i <= n; i++) 9 { 10 int l = 0, r = len + 1; 11 while (l + 1 != r) // 找小于a[i]的第一个数 12 { 13 int mid = (l + r) / 2; 14 if (f[mid] >= a[i])//因为这里维护的是最长不上升子序列 15 l = mid;//因此这里的l和r应该反着取 16 else 17 r = mid; 18 //左侧l都是>=a[i],r相反，如果r没变，说明a[len+1]=a[i]; 19 //这时候发现规定的r没变，并且r=len+1（模板的优越性），否则替换末尾值 20 } 21 f[r] = a[i]; 22 if(r == len + 1) len++; 23 } 24 cout << len << endl; 25 int cnt = 1; 26 g[cnt] = a[1];//g[i]记录的是每次子序列末尾的最小值，但是当我们发现g[mid]>=a[i]， 27 //则可以有更优越的a[i]替换末尾 28 for (int i = 2; i <= n; i++) 29 { 30 int l = 0, r = cnt + 1; 31 while (l + 1 != r) 32 { 33 int mid = (l + r) / 2; 34 if (g[mid] < a[i])//如果都是<a[i]的值，那么就需要重开系统，这时候发现 35 l = mid;//居然发现r=cnt+1，那么默认g[r]=a[i] 36 else 37 r = mid; 38 } 39 g[r] = a[i]; 40 if(r == cnt + 1) cnt ++; 41 } 42 cout << cnt << endl; 43 return 0; 44 }