BOJ)2104 부분배열 고르기

문제: icpc.me/2104

주어지는 배열에서 i~j까지의 부분 배열을 선택했을 때 (a[i]+a[i+1]+...+a[j])*(min(a[i],a[i+1]),....,a[j]) 가 최대가 되도록 i j를 선택하는 문제이다.

나이브한 풀이법으로는 i,j를 선택하는데만 O(N^2)으로 시간초과다 ..

따라서 좀 더 그리디하게 생각해보면 만약에 어떤 구간에 대해 정할 때 한 점 X를 기준으로 그 점이 최솟값이 되게 구간을 선택한다면

X를 기준으로 좌우로 최대한 X보다 큰값을 가지는 범위롤 포함하도록 배열을 선택할 수 있다.

이러한 아이디어에서 출발하여 모든 점에 대해서 이 범위를 볼건데

정렬을 해주어 작은 값부터 보면서 set에 업데이트해주어 이동가능한 lower_bound와 upper_bound를 찾아준다면 O(NlongN)에 문제를 해결할 수 있다.

소스코드에서 set에 업데이트를 해줄 때 같은 값을 한번에 업데이트 시켜주기 위하여 업데이트 할 값을 queue에 저장해주었다. 

아 참고로 구간합은 당연히 psum을 이용하여 가져와줘야 한다.

#include <cstdio>
#include <algorithm>
#include <set>
#include <queue>
using namespace std;
typedef long long ll;
set<ll> st;
queue<ll> qu;
ll n, a[100010], sum[100010], r, prv;
pair<ll, ll> p[100010];
int main() {
    scanf("%lld", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%lld", &a[i]);
        sum[i] = a[i] + sum[i - 1];
    }
    for (int i = 1; i <= n; i++)
        p[i] = { a[i],i };
    sort(p + 1, p + n + 1);
    prv = -1;
    for (int i = 1; i <= n; i++) {
        if (prv != p[i].second) {
            while (qu.size()) {
                st.insert(qu.front());
                qu.pop();
            }
        }
        if (!st.size()) {
            r = max(sum[n] * p[i].first, r);
            st.insert(p[i].second);
        }
        else {
            auto it = st.lower_bound(p[i].second);
            int lo, hi;
            if (it == st.end()) {
                it--;
                r = max((sum[n] - sum[*it])*p[i].first, r);
            }
            else {
                if (it == st.begin())
                    r = max(sum[*it - 1] * p[i].first, r);
                else {
                    auto pit = it;
                    pit--;
                    r = max((sum[*it - 1] - sum[*pit])*p[i].first, r);
                }
            }
        }
        qu.push(p[i].second);
    }
    printf("%lld\n", r);
    return 0;
}