문제

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


알고리즘

분할정복


풀이

유명한 분할정복 문제입니다. $N$제한을 고려하지 않은 채 문제를 풀어보도록 합시다. 이중 포문을 통해 모든 i, j에 대하여 문제에서 요구하는 값을 $N^2$에 해결할 수 있습니다. 하지만 이 문제의 $N$제한은 100000이므로 제곱을 하게 되면 시간초과를 면할 수 없습니다.

문제 제한을 통해 log임을 느낄 수 있습니다. $O(NlogN)$은 시간제한 1초 안에 들어올 수 있는 복잡도입니다. 분할정복으로 해결해보도록 합시다. 분할정복을 처음 접할 때 가장 어려운 부분 중 하나는 재귀를 다루는 부분입니다. 재귀함수를 작성할 시 아직 함수를 다 작성하지 않았음에도 불구하고 작동할 것이라는 믿음을 갖고 작성해야 하는 부분이 어렵습니다. $solve(i, j)$는 i와 j사이의 범위에서 원하는 답을 찾아내는 함수입니다. 즉 우리가 찾는 답은 3가지의 범위 안에 존재합니다. i와 j의 중앙값을 mid라고 하겠습니다.

  1. i~mid
  2. mid+1~j
  3. mid를 포함하는 a~b

1번과 2번은 우리가 호출하는 함수와 범위만 다를 뿐 요구하는 쿼리는 같으므로 각각 $solve(i, mid)$와 $solve(mid+1, j)$를 호출함으로써 해결 가능합니다.

3번은 다음과 같이 해결할 수 있습니다. 정답의 후보가 되는 a, b를 모두 알아내기 위해 조건에 따라 a와 b를 i와 j가 될 때까지 while문을 반복합니다. 범위를 넓혀가는 과정 중 $arr [a-1]$과 $arr[b+1]$중 이득이 되는 곳은 두 값 중 큰 쪽입니다.

$arr[a-1]$이 크다면 a를 -1 하여 i에 가깝도록, $arr [b+1]$이 크다면 b를 +1 하여 j에 가까워지도록 합시다. a와 b를 갱신했다면 그에 따라 $ret$를 계속적으로 갱신해주면 정답을 구할 수 있습니다.

코드

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define REP(i,n) for(int i=1;i<=n;++i)
#define FAST cin.tie(NULL);cout.tie(NULL); ios::sync_with_stdio(false)
using namespace std;

typedef long long ll;

int N;
ll arr[100001],psum[100001];

ll solve(int lt, int rt) {
    if (lt == rt) return arr[lt] * arr[lt];
    int mid = (lt + rt) / 2;
    ll ret = max(solve(lt, mid), solve(mid + 1, rt));

    int l = mid;
    int r = mid + 1;
    ll mn = min(arr[l], arr[r]);
    ret = max(ret, (psum[r]-psum[l-1])*mn);

    while (lt < l || r < rt) {
        if (r<rt&&(lt==l||arr[l - 1] < arr[r + 1])) {
            r += 1;
            mn = min(mn, arr[r]);
        }
        else {
            l -= 1;
            mn = min(mn, arr[l]);
        }
        ret = max(ret, (psum[r] - psum[l - 1]) * mn);
    }
    return ret;
}


int main() {
    FAST;
    cin >> N;
    REP(i, N) {
        cin >> arr[i];
        psum[i] = psum[i - 1] + arr[i];
    }
    cout<<solve(1, N);

    return 0;
}