2104번 부분배열 고르기

문제 링크

부분배열 고르기

문제 풀이

크기가 N인 1차원 배열 A가 있을 때, 어떤 $i, j (1≤i≤j≤N)$에 대한 점수는 $(A[i]+…+A[j])×Min\{A[i], …, A[j]\}$가 된다고 한다. 이때, 배열에서 가능한 최대 점수를 구하는 문제이다.
이는 FENCE와 비슷하다. 배열의 오른쪽과 왼쪽에서의 최대 점수를 찾고, 양쪽에 걸쳐진 배열의 최대 점수를 구해 최대 값을 찾으면 된다. 그리고 양쪽에 걸쳐진 문제에서 오른쪽과 왼쪽 중 어느 것을 먼저 추가할지는 두 배열의 값 중 더 큰 것부터 추가한다. 작은 것부터 추가하면 배열에서의 Min값을 찾아 곱하기때문에 손해를 본다.

구현

#include <iostream>
#include <vector>
#include<algorithm>
using namespace std;
using ll = long long;

ll N;
vector<ll> A(100000);

ll solve(ll left, ll right) {
    if (left == right) return A[left] * A[left];

    ll mid = (left + right) / 2;
    ll ret = max(solve(left, mid), solve(mid+1,right));

    ll sum = A[mid] + A[mid + 1];
    ll minValue = min(A[mid], A[mid+1]);

    ret = max(ret, sum * minValue);
    int low = mid, high = mid + 1;
    
    while (left < low || high < right) {
        if (left < low && (right == high || A[low-1] > A[high+1])) {
            --low;
            sum += A[low];
            minValue = min(minValue, A[low]);
        }
        else {
            ++high;
            sum += A[high];
            minValue = min(minValue, A[high]);
        }
        ret = max(ret, sum * minValue);
    }
    return ret;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    
    cin >> N;
    for (int i = 0; i < N; ++i)
        cin >> A[i];
    cout << solve(0, N-1);
    return 0;
}