fork(135) download
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. using namespace std;
  5.  
  6. int main() {
  7. int n;
  8. cin >> n;
  9. vector<int> a(n);
  10. for (int i = 0; i < n; i++) {
  11. cin >> a[i];
  12. }
  13. vector<int> d(n+1, 1000000000);
  14. for (int i = 0; i < n; i++) {
  15. *lower_bound(d.begin(), d.end(), a[i]) = a[i];
  16. }
  17. for (int i = 0; i <= n; i++) {
  18. if (d[i] == 1000000000) {
  19. cout << i << endl;
  20. return 0;
  21. }
  22. }
  23. }
  24.  
Success #stdin #stdout 0s 3432KB
stdin
6
4 5 1 2 2 3
stdout
3