#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
deque<int> tab(n);
int max_val = 0;
for(int i=0;i<n;i++) {
cin >> tab[i];
max_val = max(max_val, tab[i]);
}
while(tab.back() != max_val) {
tab.push_front(tab.back());
tab.pop_back();
}
stack<pair<int,int>> stos; // number, dp
int scr = 0;
for(int num: tab) {
int dpi = 1; // dp[i]
while(stos.size() && stos.top().first < num) {
dpi = max(dpi, stos.top().second + 1);
stos.pop();
}
stos.push({num, dpi});
scr = max(scr, dpi);
}
cout << scr << endl;
return 0;
}
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 | #include <bits/stdc++.h> using namespace std; int main() { ios_base::sync_with_stdio(0); cin.tie(0); int n; cin >> n; deque<int> tab(n); int max_val = 0; for(int i=0;i<n;i++) { cin >> tab[i]; max_val = max(max_val, tab[i]); } while(tab.back() != max_val) { tab.push_front(tab.back()); tab.pop_back(); } stack<pair<int,int>> stos; // number, dp int scr = 0; for(int num: tab) { int dpi = 1; // dp[i] while(stos.size() && stos.top().first < num) { dpi = max(dpi, stos.top().second + 1); stos.pop(); } stos.push({num, dpi}); scr = max(scr, dpi); } cout << scr << endl; return 0; } |
English