[ BOJ 백준 2104번 - 부분배열 고르기 ] 해설 및 코드

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

2104번: 부분배열 고르기

목적

어떤 i, j(1≤i≤j≤N)에 대하여, (A[i]+…+A[j])×Min{A[i], …, A[j]} 와 같은 식의 최대값을 구한다.

 

접근법

1. 스위핑 알고리즘으로 O(n)에 문제를 해결해보자.(백준 1725 - 히스토그램 문제처럼 분할 정복 알고리즘으로도 접근 가능하다.)

2. 부분합은 전처리 과정을 통해, 스위핑 알고리즘 적용시 O(1)의 시간복잡도에 해결하자.

 

#include<iostream>
 
using namespace std;
typedef long long ll;
 
int a[100002] = {-1};
ll psum[100001] = {0};
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int n; cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        psum[i] = psum[i - 1] + a[i];
    }
    a[++n]=0;
    
    ll ret=0;
    int s[100002] ={0},top=0;
    for (int i = 1; i <= n; ++i){
        while(a[s[top]]>=a[i]){
            int height=a[s[top--]];
            ll val=height*(psum[i-1]-psum[s[top]]);
            if(ret<val)ret=val;
        }
        s[++top]=i;
    }
    cout<<ret;
}
 

 

문제 설명과 코드에 대한 피드백은 언제나 환영합니다.

 다양한 의견 댓글로 남겨주세요.