CSES Advertisement

這邊貼上CSES的一些筆記, 好讓日後可以回來複習

這題跟lc第84題一模一樣, 可以先去看lc再回來看這題

#include <iostream>
#include <stack>
#include <vector>
using namespace std;
int main() {
    int n;
    std::cin >> n;
    vector<long long> arr(n, 0);
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    stack<long long> st;
    long long res = 0;
    arr.push_back(0);
    for (int i = 0; i < n + 1; i++) {
        if (st.empty() || arr[st.top()] < arr[i]) {
            st.push(i);
        } else {
            auto cur = st.top();
            st.pop();
            res = max(res, arr[cur] * (st.empty() ? i : i - st.top() - 1));
            i--;
        }
    }
cout << res << "\n";
    return 0;
}