백준 1912 - 연속합

문제

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

1912번: 연속합

 

풀이

연속된 수열 중 최대 값을 찾아야 하는 문제이다.

 

수열을 처음부터 차례로 더하면서 더한 결과가 0보다 크면 우선순위 큐에 저장을 한다. 만약 더한 결과가 0보다 작으면 그 수열 조합은 최대값이 될 수 없으므로, 그 다음 값 부터 수열을 시작해서 다시 최대값을 찾는다.

 

만약 우선순위 큐가 비었다면 배열에는 0보다 큰 값이 없는 것이다. 따라서 배열을 내림차순으로 정렬하면 된다.

 

 

코드

c++

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
 
using namespace std;
 
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
 
    int n;
    cin >> n;
 
    vector<int> v;
    while (n--)
    {
        int num;
        cin >> num;
        v.push_back(num);
    }
 
    priority_queue<int> pq;
 
    int result = 0;
    for (int i = 0; i < v.size(); i++)
    {
        if ((v[i] < 0) && (result + v[i] < 0))
        {
            result = 0;
            continue;
        }
 
        result += v[i];
        pq.push(result);
    }
 
    if (pq.empty())
    {
        sort(v.begin(), v.end(), greater<int>());
        cout << v[0];
    }
    else
        cout << pq.top();
 
    return 0;
}