[BAEKJOON 2104번] (C++) 부분배열 고르기

www.acmicpc.net/problem/2104

2104번: 부분배열 고르기

 

분할 정복을 통해 해결

 

1. mid 를 중심으로 왼쪽 부분배열의 최대값

2. mid 를 중심으로 오른쪽 부분배열의 최대값

3. mid를 포함한 부분배열의 최대값

중 가장 큰 값을 출력

 

#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;
	//1. 왼쪽 부분배열의 최대값
	long long leftSum = GetMax(from, mid);
	//2. 오른쪽 부분배열의 최대값
	long long rightSum = GetMax(mid + 1, to);

	//1+2.왼쪽, 오른쪽 부분배열의 최대값
	long long maxValue = max(leftSum, rightSum);

	
	int left = mid;
	int right = mid + 1;

	long long sum = A[left] + A[right];
	long long minValue = min(A[left], A[right]);
	// 최대 값 비교

	maxValue = max(maxValue, sum * minValue);

	//3. mid를 포함한 부분배열의 최대값
	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);
	}

	//1+2+3 . 세 가지 경우 중 최대값을 구하여 저장
	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;
}