#include <bits/stdc++.h>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; ++i)
{
cin >> a[i];
}
vector<int> values(n);
vector<int> counts(n);
values[0] = a[0];
counts[0] = 1;
for (int i = 1; i < n; ++i)
{
values[i] = values[i - 1];
counts[i] = counts[i - 1];
if (a[i] > values[i])
{
values[i] = a[i];
++counts[i];
}
}
int answer = counts[n - 1];
vector<int> current;
for (int i = n - 1; i > 0; --i)
{
while (!current.empty() && current.back() <= a[i]) current.pop_back();
current.push_back(a[i]);
int pos = upper_bound(values.begin(), values.begin() + i - 1, current[0]) - values.begin();
if (a[pos] <= current[0])
{
answer = max(answer, (int) current.size());
continue;
}
int additional = counts[i - 1];
if (pos > 0) additional -= counts[pos - 1];
answer = max(answer, (int) current.size() + additional);
}
cout << answer << '\n';
}
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 | #include <bits/stdc++.h> using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(0); int n; cin >> n; vector<int> a(n); for (int i = 0; i < n; ++i) { cin >> a[i]; } vector<int> values(n); vector<int> counts(n); values[0] = a[0]; counts[0] = 1; for (int i = 1; i < n; ++i) { values[i] = values[i - 1]; counts[i] = counts[i - 1]; if (a[i] > values[i]) { values[i] = a[i]; ++counts[i]; } } int answer = counts[n - 1]; vector<int> current; for (int i = n - 1; i > 0; --i) { while (!current.empty() && current.back() <= a[i]) current.pop_back(); current.push_back(a[i]); int pos = upper_bound(values.begin(), values.begin() + i - 1, current[0]) - values.begin(); if (a[pos] <= current[0]) { answer = max(answer, (int) current.size()); continue; } int additional = counts[i - 1]; if (pos > 0) additional -= counts[pos - 1]; answer = max(answer, (int) current.size() + additional); } cout << answer << '\n'; } |
English