백준 2104 - 부분배열 고르기

문제

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

2104번: 부분배열 고르기

 

풀이

이유 : 가운데를 걸치는 부분배열에서 최대값을 구할 때 시간초과가 났다.

 

최대 부분 배열을 고르는 알고리즘은 분할 정복을 이용한다.

가운데를 기준으로 1.왼쪽 부분 배열 2.오른쪽 부분 배열 3.가운데에 걸치는 부분 배열 총 3가지 경우가 나온다. 이 세가지 중 가장 큰 값을 반환하는 부분 배열이 답이 된다.

가운데 걸치는 부분 배열을 구할 때는 배열에 중간에서 시작해서 왼쪽 또는 오른쪽으로 1칸씩 확장해 나가야 한다. 이 때 왼쪽, 오른쪽 중 큰 쪽으로 확장을 해야한다. 1칸씩 확장해 나가면서 현재까지의 최대값과 비교한다.

 

코드

#include <iostream>
#include <algorithm>
 
using namespace std;
 
const int MAX = 1000001;
 
int N;
int A[MAX];
 
long long GetMax(int from, int to)
{
    // 기저 사례
    if (from == to) return (long long)A[from] * A[from];
 
    int mid = (from + to) / 2;
    long long leftSum = GetMax(from, mid);
    long long rightSum = GetMax(mid + 1, to);
 
    // 왼쪽, 오른쪽 부분배열 중 최대를 찾음
    long long maxValue = max(leftSum, rightSum);
 
    int left = mid;
    int right = mid + 1;
 
    // mid에서 시작하는 교차하는 부분 배열
    long long sum = A[left] + A[right];
    long long minValue = min(A[left], A[right]);
    // 최대 값 비교
    maxValue = max(maxValue, sum * minValue);
 
    // 교차 하는 부분 배열에서 최대를 찾음
    while (left > from || right < to)
    {
        // 오른쪽으로 증가
        if (right < to && (left == from || A[left - 1] < A[right + 1]))
        {
            sum += A[++right];
            minValue = min(minValue, (long long)A[right]);
        }
        else    // 왼쪽으로 증가
        {
            sum += A[--left];
            minValue = min(minValue, (long long)A[left]);
        }
        long long crossSum = sum * minValue;
        // 최대 값 비교
        maxValue = max(maxValue, crossSum);
    }
    
    return maxValue;
}
 
int main() 
{
    cin.tie(0);
    ios::sync_with_stdio(false);
 
    cin >> N;
    for (int i = 1; i <= N; i++) cin >> A[i];
 
    cout << GetMax(1, N);
 
    return 0;
}