챕터3-16. DP | 문제 풀이3 - (5) 백준 No.1912 : 연속합

연속합 문제

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

문제요약

n개의 정수로 이루어진 임의의 수열이 주어지면
이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하라.
ex) A = {10, -4, 3, 1, 5, 6, -35, 12, 21, -1}
      연속된 수들의 합 중 가장 큰 값은 12 + 21 = 33

해결 방법

1. D[i] 정의
D[i] = "A[i]로 끝나는(까지 왔을 때의) 최대 연속합" 으로 정의할 수 있고,

A[i]로 끝나는 최대 연속합은 두가지의 경우가 될 수 있다.
1) A[i-1]로 끝나는 최대 연속합에 A[i]가 포함되는 경우  => D[i-1] + A[i]
2) A[i]가 새로운 수열의 합으로 시작하는 경우                 => A[i] 

 

그러면 D[i] = max (D[i-1] + A[i], A[i]) 가 된다.

 

@ 위의 점화식을 그림으로 이해하기 위한 예시

따라서 D의 최대값인 33이 정답이 된다.

<Bottom-up 방식>

(1)시간복잡도
= for 문의 반복 횟수 

이 방법을 사용하면 N개의 칸을 채워야 하고, 한칸 D[i]의 값을 채울 때 비교는 D[i-1]+A[i]와 한번만 일어나므로 
시간복잡도는 O(N)이 된다. 따라서 1중 for문으로 구현이 가능하다.

 

(2) 구현
-> 'for문을 이용한 반복문'으로 구현

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int main()
{
    int n;
    cin >> n;

    vector<int> a(n);
    vector<int> d(n);

    for (int i = 0; i < n; i++)
        cin >> a[i];

    d[0] = a[0];

    for (int i = 1; i < n; i++)
        d[i] = max(d[i-1] + a[i], a[i]);

    cout << *max_element(d.begin(), d.end()) << "\n";
}