백준 2104번 부분배열 고르기

www.acmicpc.net/problem/2104

 

 

 

 

<접근방법>

왼쪽 부분, 오른쪽  부분, 가운데 부분 중에서 최대값을 찾는다.

 

---

 

 

 

<코드>

#include <iostream>
#include <algorithm>
using namespace std;

#define MAX 100001
#define INF 987654321


int n;
long long A[MAX];

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

	int mid = (left + right) / 2;

	long long res = max(solve(left, mid), solve(mid + 1, right));

	int low = mid;
	int high = mid+1;
	long long m = min(A[low], A[high]);
	long long sum = A[low] + A[high];

	res = max(res, (sum * m));

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

int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> A[i];
	}

	cout << solve(0, n-1) << '\n';

	return 0;
}