BOJ 1989 - 부분배열 고르기 2

문제 링크 : https://www.acmicpc.net/problem/1989

문제 풀이

수열에 있는 각 수 별로 그 수가 최솟값인 최대 배열을 잡을 수 있으면 문제를 풀 수 있다. 옛날에 풀었던 문제가 생각났고, 풀이가 바로 생각났다.

 어떠한 수열 조각에 대해서 최솟값을 잡는다. 그럼 그 때 그 최솟값에 대한 값은 그 값 * 수열 조각의 구간합이다. 이때 다른 임의의 값은 그 최솟값을 포함하면 그 값이 최솟값이 될 수 없다. 따라서 수열 조각에서 최솟값 부분을 빼면서 수열을 쪼갤 수 있다. 이런식으로 수열을 계속 쪼개나가면서 값을 구하면 된다.
 구간 최솟값과 구간 합은 둘다 segment tree를 이용하여 구할 수 있다.

 그리고 구현이 더 쉬운 다른 풀이가 생각났다. 결국 수열의 모든 값에 대해서 그 값이 최솟값이 되는 가장 큰 수열의 구간을 구하는 것이 목표이다.
 Monotone queue technique를 이용하자. O(N)에 모든 값에 대해 그 인덱스에 오른쪽에 존재하며 그 값보다 작은 가장 왼쪽에 있는 값의 위치를 구할 수 있다. 즉, 그 값이 최솟값이 더이상 아니게 되는 시점을 구할 수 있다는 것이다. 이를 좌우에 대해서 반복하면 모든 값에 대해서 최대 수열의 구간을 구할 수 있고, prefixsum을 이용하여 구간의 합을 미리 구해 놓으면 최종 O(N)에 해결이 가능하다. 

코드

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> pii;
typedef pair<pii,ll> piii;
#define ff first
#define ss second
#define ep emplace_back
#define eb emplace
#define pb push_back
#define all(v) v.begin(), v.end()
 
ll arr[1010101];
ll l[101010];
ll r[101010];
ll pre[101010];
stack<pii> s1;
stack<pii> s2; 
 
int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    ll i,j,k,m,n;
 
    cin>>n;
    for(i=1;i<=n;i++){
        cin>>arr[i];
        pre[i]=pre[i-1]+arr[i];
    }
 
    for(i=1;i<=n;i++){
        while(s1.size()&&s1.top().ff>arr[i]){
            ll x=s1.top().ss;
            r[x]=i-1;
            s1.pop();
        }
        s1.push({arr[i],i});
    }
 
    while(s1.size()){
        ll x=s1.top().ss;
        r[x]=n;
        s1.pop();
    }
 
    for(i=n;i>=1;i--){
        while(s2.size()&&s2.top().ff>arr[i]){
            ll x=s2.top().ss;
            l[x]=i+1;
            s2.pop();
        }
        s2.push({arr[i],i});
    }
 
    while(s2.size()){
        ll x=s2.top().ss;
        l[x]=1;
        s2.pop();
    }
    ll ans=0;
    ll x1=1,x2=n;
    for(i=1;i<=n;i++){
        if(ans<(pre[r[i]]-pre[l[i]-1])*arr[i]){
            ans=(pre[r[i]]-pre[l[i]-1])*arr[i];
            x1=l[i];
            x2=r[i];
        }
    }
 
    cout<<ans<<'\n';
    cout<<x1<<' '<<x2;
 
}