#include <bits/stdc++.h>
using namespace std;
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(NULL);
int n;
cin >> n;
vector<int> per(2 * n + 1);
for (int i = 1; i <= n; i++)
{
cin >> per[i];
per[i + n] = per[i];
}
priority_queue<pair<int, int>> no_next;
vector<int> dp(2 * n, 1);
int max_dp = 0;
for (int i = 1; i < 2 * n; i++)
{
while (!no_next.empty() && no_next.top().first > -per[i])
{
int oj = no_next.top().second;
no_next.pop();
dp[i] = max(dp[i], dp[oj] + 1);
}
max_dp = max(max_dp, dp[i]);
no_next.push({-per[i], i});
}
cout << max_dp << "\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 | #include <bits/stdc++.h> using namespace std; int main() { ios_base::sync_with_stdio(0); cin.tie(NULL); int n; cin >> n; vector<int> per(2 * n + 1); for (int i = 1; i <= n; i++) { cin >> per[i]; per[i + n] = per[i]; } priority_queue<pair<int, int>> no_next; vector<int> dp(2 * n, 1); int max_dp = 0; for (int i = 1; i < 2 * n; i++) { while (!no_next.empty() && no_next.top().first > -per[i]) { int oj = no_next.top().second; no_next.pop(); dp[i] = max(dp[i], dp[oj] + 1); } max_dp = max(max_dp, dp[i]); no_next.push({-per[i], i}); } cout << max_dp << "\n"; } |
English