2024/12/29 일 매일백준

오늘의 문제는

1912번: 연속합

이다.

연속하여 더한 값 중 최대값을 출력하라는 문제이다.

주의해야할 점은 연속합에 음수가 포함되어있어도 최대값이 될 수도 있다는 것이다.
예를 들어, 30 -20 120 이라면은 세 수를 더한 130이 최대값이 되기 때문에 이를 고려해야한다.
그래서 연속합을 갱신할 때는 연속합보다 현재값이 더 클 경우에만 갱신을 하면됨. 이래야 음수값이 포함된 연속합을 저장하면서 음수값이 포함된 최대값을 고려할 수 있다.

아래의 예시를 통하여 점화식을 찾아보자.

입력
$10\\ 10-4\,\, 3\,\, 1\,\, 5\,\, 6-35\,\,12\,\, 21\,\, -1$

1번째 : 최댓값은 10, 연속합도 10
2번째 : 최댓값은 10, 연속합은 max(10 + (-4), -4)는 6
3번째 : 최대값은 10, 연속합은 max(6 + 3, 3) 는 9
4번째 : 최대값은 10, 연속합은 max(9 + 1, 1)는 10
5번째 : 최대값은 15, 연속합은 max(10 + 5, 5)는 15
6번째 : 최대값은 21, 연속합은 max(15 + 6, 6)는 21
7번째 : 최대값은 21, 연속합은 max(21 + (-35), -35)는 -14
8번째 : 최대값은 21, 연속합은 max(-14 + 12, 12)는 12
---->여기서 연속합의 갱신이 발생
9번째 : 최대값은 33, 연속합은 max(12 + 21, 21)는 33
10번째 : 최대값은 33, 연속합은 max(33 + (-1), -1)는 32

따라서 출력은 33이 된다.

위 과정을 통해서 점화식을 작성해보면은

다음과 같다.

#include <iostream>
#include <algorithm>

using namespace std;

int main(void) {

    int n, num[100001] = {0}, dp[100001] = {0}, res;

    cin >> n;

    for(int i=1;i<=n;i++) {
        cin >> num[i];
    }

    res = num[1];
    dp[1] = num[1];

    for(int i=2;i<=n;i++) {
        dp[i] = max(dp[i - 1] + num[i], num[i]);
        res = max(res, dp[i]);
    }
    
    cout << res << endl;

    return 0;
}

끝.