[BOJ] 2104. 부분배열 고르기

2104. 부분배열 고르기

1. 문제

크기가 N(1 ≤ N ≤ 100,000)인 1차원 배열 A[1], …, A[N]이 있다. 어떤 i, j(1 ≤ i ≤ j ≤ N)에 대한 점수는, (A[i] + … + A[j]) × min{A[i], …, A[j]}가 된다. 즉, i부터 j까지의 합에 i부터 j까지의 최솟값을 곱한 것이 점수가 된다.

배열이 주어졌을 때, 최대의 점수를 갖는 부분배열을 골라내는 프로그램을 작성하시오.

2. 입력

첫째 줄에 정수 N이 주어진다. 다음 줄에는 A[1], …, A[N]을 나타내는 정수들이 주어진다. 각각의 정수들은 음이 아닌 값을 가지며, 1,000,000을 넘지 않는다.

3. 출력

첫째 줄에 최대 점수를 출력한다.

4. 풀이

C++

#include <iostream>
#include <stack>
#include <utility>
using namespace std;
typedef pair<long, int> p;
#define MAX 100001

int N;
p point[MAX]; // 좌표 집합

// 정사각형 히스토그램
long Solve()
{
    stack<p> remaining;
    long ans = 0;
    
    for (int i = 0; i <= N; ++i)
    {
        while (!remaining.empty() && remaining.top().second >= point[i].second)
        {
            p j = remaining.top();
            remaining.pop();
            
            long width = -1;
            if (remaining.empty()) width = point[i].first - point[i].second;
            else width = point[i].first - remaining.top().first - point[i].second;
            
            ans = max(ans, j.second * width);
        }
        
        remaining.push(point[i]);
    }
    
    return ans;
}


int main()
{
    cin >> N;
    int a;
    long sum = 0;
    
    for (int i = 0; i < N; ++i)
    {
        cin >> a;
        sum += a;
        point[i] = make_pair(sum, a);
    }
    point[N] = make_pair(sum, 0); // 마지막에 크기 0인 정사각형 삽입
    
    cout << Solve() << endl;
}