BOJ 2104 부분배열 고르기

문제

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

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

주어진 배열에서  \( (A[i]+…+A[j])\times min({A[i], …, A[j]}) \) 가 최대가 되도록 고르는 문제이다.

풀이

이 문제는  \( min({A[i], …, A[j]}) \) 를 곱한다는 면에서 히스토그램 문제와 매우 유사하다. (!!!)

따라서 이문제는 그냥 히스토그램 변형 문제이다.

 

이와 같이 히스토그램을 설정하되, 모든 그래프는 정사각형이라 하면 문제의 조건을 만족한다.

또한, 증명도 각 정사각형을 가로 길이 1의 도막으로 쪼개 적용하면 똑같이 성립함을 알 수 있다.

구현은 히스토그램과 거의 똑같다.

 

시간 복잡도 : $O(NlogN)$

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define MAXN 100000

int n;
ll arr[MAXN+10];

struct Form
{
    ll v;
    int l, r;

    Form() {}
    Form(ll v, int l, int r) : v(v), l(l), r(r) {}
    bool operator < (const Form p) const
    {
        return v<p.v;
    }
};
Form ans(-1, 0, 0);

void solve(int s, int e)
{
    if(s==e)
    {
        ans=max(ans, Form(arr[s]*arr[s], s, e));
        return;
    }

    int mid=(s+e)/2;
    solve(s, mid);
    solve(mid+1, e);

    ll minval=min(arr[mid], arr[mid+1]), sum=arr[mid]+arr[mid+1];
    Form now=Form(sum*minval, mid, mid+1);
    int l=mid, r=mid+1;
    while(s<l || r<e)
    {
        if(r<e && (l==s || arr[l-1]<arr[r+1]))
        {
            r++;
            sum+=arr[r];
            minval=min(minval, arr[r]);
        }
        else
        {
            l--;
            sum+=arr[l];
            minval=min(minval, arr[l]);
        }
        now=Form(sum*minval, l, r);
        ans=max(ans, now);
    }
}

int main()
{
    cin.tie(0); cout.tie(0);
    ios_base::sync_with_stdio(false);
    int i;

    scanf("%d", &n);
    for(i=1; i<=n; i++) scanf("%d", &arr[i]);

    solve(1, n);
    printf("%lld\n%d %d", ans.v, ans.l, ans.r);
    return 0;
}