문제#

풀이#

  1. 제일 작은 단위 N = 2 까지 분할한다
  2. 분할된 부분을 반으로 나누어, left의 최댓값, right의 최댓값을 구한다
  3. 분할된 부분에서 left와 right를 걸치는 경우의 최댓값을 구한다 (그리디? O(N)의 시간복잡도)
  4. 분할 전으로 돌아가서 1 - 3 을 반복한다

얼핏 보면 O(N^2) 같지만 분할하고 이를 다시 합치는 과정이 O(logN) 걸치는 경우를 구하는 과정이 O(N)이므로 최종적으로는 O(NlogN) 이다!

매번 모든 요소를 기준으로 확장하며 최댓값을 구하는 과정은 O(N^2)이므로
조금 더 효율적이지 않을까?


#include <bits/stdc++.h>
#define ll long long

using namespace std;

int N;
ll arr[100001];

ll solve(int start, int end) {

    if (start == end)
    	return arr[start] * arr[start];

    int mid = (start + end) / 2;
    int left = mid, right = mid + 1;

    ll result = max(solve(start, left), solve(right, end));

    ll min_val = min(arr[left], arr[right]);
    ll tsum = arr[left] + arr[right];
    ll tresult = tsum * min_val;

    while (left > start || right < end) {

    	if (right < end && (left == start || arr[left - 1] < arr[right + 1])) {
    		right++;
    		min_val = min(min_val, arr[right]);
    		tsum += arr[right];
    	}

    	else {
    		left--;
    		min_val = min(min_val, arr[left]);
    		tsum += arr[left];
    	}

    	tresult = max(tresult, tsum * min_val);
    }

    return (max(result, tresult));

}

int main() {
cin.tie(0);
ios::sync_with_stdio(0);

    cin >> N;

    for (int i = 0; i < N; i++) cin >> arr[i];

    cout << solve(0, N - 1);

}
🗪 댓글