Untitled

 avatar
unknown
plain_text
10 months ago
1.1 kB
16
Indexable
#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>

using namespace std;

int main() {
    int n;
    cin >> n;

    vector<int> v(n);

    for (int i = 0; i < n; ++i) {
        cin >> v[i];
    }

    stack<pair<int, int>> st;
    int maxD = 0;

    for (int i = 0; i < n; ++i) {
        if (st.empty()) {
            st.push({v[i], 0});
        } else {
            auto top = st.top();

            if (v[i] > top.first) {
                int days = 1;
                maxD = max(maxD, days);
                st.push({v[i], days});
            } else {
                int maxi = 0;
                while (!st.empty() && st.top().first >= v[i]) {
                    maxi = max(maxi, st.top().second);
                    st.pop();
                }

                if (st.empty()) {
                    st.push({v[i], 0});
                } else {
                    st.push({v[i], maxi + 1});
                    maxD = max(maxD, maxi + 1);
                }
            }
        }
    }

    cout << maxD << endl;

    return 0;
}
Editor is loading...
Leave a Comment