2104번: 부분배열 고르기

https://www.acmicpc.net/problem/2104


문제는 히스토그램 내 가장 큰 직사각형 구하기와 동치이다.

$O(n\lg n)$

#include<cstdio>
#include<set>
#include<algorithm>
using namespace std;
const int MXN = 1e5;
int n;
long long s[MXN + 1], res;
pair<int, int> p[MXN + 1];
set<int> st;
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &p[i].first), p[i].second = i, s[i] = s[i - 1] + p[i].first;
    sort(p + 1, p + 1 + n);
    st.insert(0); st.insert(n + 1);
    for (int i = 1; i <= n; i++) {
        auto t = st.upper_bound(p[i].second);
        res = max(res, (s[*t - 1] - s[*--t])*p[i].first);
        st.insert(p[i].second);
    }
    printf("%lld", res);
    return 0;
}