BOJ - 2104 부분배열 고르기

2104번 부분배열 고르기
배열이 주어지고 해당 배열에서 최대 점수를 갖는 부분 배열을 골라내는 문제이다.

점수 계산 방법은 i,j(1<=i<=j<=N)에 대하여 (i부터 j까지의 합)X(i부터 j까지의 최소 값)의 식을 통해 구한다.

문제 해결 과정
일반 반복문으로 해결하기에는 배열의 크기가 커질 경우 엄청난 반복횟수로 인한 시간초과가 우려된다.

분할정복을 통해 시간초과 문제를 해결할 수 있다.

왼쪽에서 가장 큰 점수를 갖는 부분 배열과 오른쪽에서 가장 큰 점수를 갖는 부분배열, 그리고 가운데에서 부터 양 쪽으로 뻗어나가 가장 큰 점수를 갖는 부분배열 을 비교하여 갱신해 나가는 것이다.

왼쪽과 오른쪽에서의 값을 구하기 위해서는 재귀호출을 하면 된다. (시작점, 중간점)과 (중간점+1, 끝점)을 매개변수로 넘겨서 호출하면 된다.

가운데에서 부터의 값을 구하기 위해서는 중간점 기준으로 양 쪽으로 뻗어나가면 되는데, 뻗어나가는 방향은 양 쪽 값중 더 큰 쪽으로 뻗어나가면 된다.

코드

#include <iostream>
#include <algorithm>

using namespace std;

int arr[100001];
long long cal(int s, int e)
{
    int middle = (s+e)/2;
    long long left;
    long long right;
    if(s != e) // 정복
    {
    	//왼쪽과 오른쪽 중 더 큰값
        left = cal(s,middle);
        right = cal(middle+1,e);
        long long tmp = max(left,right);

	// 가운데에서 부터 뻗어나가기
        int l = middle;
        int r = middle+1;
        long long sum = arr[l]+arr[r];
        long long m = min(arr[l],arr[r]);
        long long Max = sum*m;

        while(l > s || r < e)
        {
            if(r < e && (l == s || arr[l-1] < arr[r+1]))
            {
                r++;
                m = min(m,(long long)arr[r]);
                sum += arr[r];
                Max = max(Max,m*sum);
            }
            else
            {
                l--;
                m = min(m,(long long)arr[l]);
                sum += arr[l];
                Max = max(Max,m*sum);
            }

        }

	//왼쪽, 오른쪽, 가운데 중 가장 큰 값
        Max = max(Max,tmp);

        return Max;
    }else // 분할 끝까지 다 했을 때
    {
        return (long long)arr[s]*arr[s];
    }
}

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

    int n;
    cin >> n;

    for(int i=1;i<=n;i++)
    {
        cin >> arr[i];
    }

    cout << cal(1,n) << "\n";
    return 0;
}

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