알고리즘 :: 백준 :: DP :: 1912 :: 연속합

문제

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

문제접근

1. Bruteforce방법이 자연스럽게 떠오르고, 만들어지는 조합의 합을 어딘가에 기록해둔 뒤 다음에 써먹는 방법이 유효한 전형적인 DP 문제다.
2. i번째 인덱스의 요소를 그대로 두는 것과 i-1번째 인덱스까지의 합에 i번째 인덱스의 요소를 더한 값을 비교해서 더 큰 값을 메모해두면 된다.
   
3. 다음과 같은 테스트 입력에서 우리는 dp배열을 만들고 각 인덱스에서의 최대 합을 메모할것이다.
4. 10 + (-4)를 한 값 6과 -4를 비교한다. 즉, 자기 자신보다 이전 값에서 더해진 값이 더 나은 것이므로 기록한다.
   
5. -14 + 12 = -2와 12를 비교한다. 이전 값에서 더한 값보다 자기 자신이 더 큰 값이므로 굳이 더할 필요가 없다. 따라서 새로운 연속합 시작 지점이 된다.

코드

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

int q1912(const vector<int>& vec) {
    vector<int> dp(vec.size());
    dp[0] = vec[0];

    // (이전 dp값 + 현재 값)과 현재 값을 비교해서 더 큰 쪽을 메모한다. 
    for (int i = 1; i < vec.size(); ++i)
        dp[i] = max(dp[i - 1] + vec[i], vec[i]);
    sort(begin(dp), end(dp));

    return dp.back();
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);

    int n; cin >> n;   // 요소 개수
    vector<int> vec(n);
    for (int i = 0; i < n; ++i) cin >> vec[i];

    cout << q1912(vec) << '\n';
}

결과