[BOJ 2104] 부분배열 고르기

1) 문제 링크

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

2) 접근

분할 정복 알고리즘을 이용했다. 1725번 문제와 접근 방식, 풀이가 매우 유사하며 마찬가지로 시간복잡도 $O(NlogN)$으로 풀었다.

3) 풀이

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

long long N, A[100000];

long long MaxScore(int s, int e){
    if(s == e) { return 0; }
    if(s+1 == e) { return A[s]*A[s]; }

    int mid = (s+e)/2;
    long long result = max(MaxScore(s, mid), MaxScore(mid, e));

    long long sum = A[mid], min_val = A[mid];
    int l = mid, r = mid;
    while(r-l+1 < e-s){
        int p = (l>s) ? A[l-1] : -1;
        int q = (r<e-1) ? A[r+1] : -1;

        if(p >= q){
            --l;
            sum += A[l];
            min_val = min(min_val, A[l]);
        }
        else{
            ++r;
            sum += A[r];
            min_val = min(min_val, A[r]);
        }

        result = max(result, sum*min_val);
    }
    return result;
}

int main(void){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> N;
    for(int i=0; i<N; ++i){
        cin >> A[i];
    }
    cout << MaxScore(0, N);
    return 0;
}

4) 피드백

마찬가지로 스위핑 알고리즘을 이용할 수 있는 문제였다. 스택을 이용해서.
‘재미지’님의 코드. 12ms가 뜬다고 한다.