BOJ 2104 부분배열 고르기

문제링크 : https://www.acmicpc.net/problem/2104

2104번: 부분배열 고르기

요약

크기가 N의 1차워 배열의 부분배열의 합과 부분배열에서의 최솟값의 곱의 최대값을 구하는 문제

풀이

완전 탐색으로 해결하기에는 시간초과가 우려된다. 분할정복을 통해 해결해보았다. 두 부분으로 나눠서 왼쪽에서 가장 큰 점수를 갖는 부분 배열과 오른쪽에서 가장 큰 점수를 갖는 부분배열을 비교해준다. 또 양쪽에 걸치는 경우도 고려를 해줘야 한다. 왼쪽과 오른쪽에서의 최댓값은 재귀호출을 통해서 구해주었고, 가운뎃 값은 중간점을 기준으로 양쪽 값중 더 큰쪽으로 뻗어나가면서 구해주면 된다.

코드

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;
vector<ll>v;
ll n, num;
ll go(ll a, ll b) {
	if (a == b)return v[a] * v[b];
	ll m = (a + b) / 2;
	ll l = m - 1;
	ll r = m+ 1;
	ll sum = v[m];
	ll small = v[m];
	ll ans = v[m] * v[m];
	while (a <= l || b >= r) {
		if (a > l) {
			small = min(small, v[r]);
			sum += v[r++];
		}
		else if (b < r) {
			small = min(small, v[l]);
			sum += v[l--];
		}
		else if (v[l] < v[r]) {
			small = min(small, v[r]);
			sum += v[r++];
		}
		else {
			small = min(small, v[l]);
			sum += v[l--];
		}
		ans = max(ans, small*sum);
	}
	ans = max(ans, max(go(a, m), go(m + 1, b)));
	return ans;
}
int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> num;
		v.push_back(num);
	}
	cout << go(0, n - 1);
}