[BOJ/C++] 연속합(1912번)

1. 개요

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

1912번: 연속합

1-1. 설명

n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇개의 수를 선택해 구할 수 있는 합 중 가장 큰 합을 구하려 한다. 단, 수는 한 개이상 선택해야 한다. 

1-2. 제한 사항

 - 첫 줄에 정수 n이 주어지며, n은 1 이상 100,000 이하

 - 둘째 줄에는 n개의 정수로 이루어진 수열이 주어지며, 수는 -1,000 이상 1,000 이하

---

2. 구현

2-1. 풀이

시간 제한이 1초이므로, 단순히 브루트포스를 이용하면 당연히 시간초과가 난다. DP를 이용해서 풀면 될것 같았는데, 점화식이 자꾸 틀리는 것 같아 식은 다른 사람의 풀이를 참조하였다. DP 연습을 조금 더 해야할 것 같다. 

2-2. 코드 

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

constexpr size_t MAX_NUM = 100000;
int nums[MAX_NUM];

int main() // 1912
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    // n개의 정수로 이루어진 임의 수열 주어짐
    // 이중 몇개 수를 선택해 가장 큰 합 구함

    int N, maxNum;
    cin >> N;

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

    // DP Bottom-up
    // 이전 합 + 현재수 합과 현재수를 비교하여 더 큰 것을 선택
    // 이전 합 + 현재수 > 현재수 -> 현재 숫자를 이전 합에 포함
    // 이전 합 + 현재수 < 현재수 -> 현재 숫자로 새로 합을 생성
    
    for (int i = 1; i < N; i++) {
        nums[i] = max(nums[i], nums[i - 1] + nums[i]);
        if (maxNum < nums[i]) maxNum = nums[i];
    }
    cout << maxNum;


    return 0;
}