Cod sursa(job #3135193)
| Utilizator | Data | 2 iunie 2023 11:47:47 | |
|---|---|---|---|
| Problema | Subsir crescator maximal | Scor | 50 |
| Compilator | cpp-64 | Status | done |
| Runda | Arhiva educationala | Marime | 0.53 kb |
#include <fstream>
#include <vector>
#define int long long
using namespace std;
ifstream cin("scmax.in");
ofstream cout("scmax.out");
vector<int>v;
vector<int>ans;
int32_t main() {
int n;
cin >> n;
for (int i = 0; i < n; ++i) {
int x;
cin >> x;
v.push_back(x);
}
ans.push_back(v[0]);
for (int i = 1; i < n; ++i) {
if (v[i] > ans.back())
ans.push_back(v[i]);
else {
int low = lower_bound(ans.begin(), ans.end(), v[i]) - ans.begin();
ans[low] = v[i];
}
}
cout << ans.size();
return 0;
}