[알고리즘 문제] 백준1912 - 연속합

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

1912번: 연속합

코테는 보면 언제간 한번은 나올 법한 문제인 것 같다.

수열이 주어졌을 때, 이 중 몇개의 연속된 숫자를 선택해서 더한 최대합을 구하는 문제이다. 

 

먼저 2개의 배열이 필요하다. arr[]에는 입력받은 숫자들을 넣어주고, dp[i]에는 0~i번째 까지의 연속합 중에서 최대값을 저장한다. 그렇다면 그 최대값에 arr[i]번째 값을 더했을 때 값이 증가할 수도 있고, 증가하지 않을 수도 있다. 그렇기 때문에 두 경우 중 최선의 값을 dp[i]에 넣으면 된다.

 

우리는 각 arr[]의 숫자n에 할 수 있는 연산으로 2가지의 경우가 있다.

 

1. 최대값에 arr[i]를 더한다 : dp[n-1] + arr[i]

2. 최대값에 arr[i]를 더하지 않는다 : arr[i]

 

-> dp[n] = max(dp[n-1] + arr[i], arr[i])

 

위의 두 경우 중에 dp[i]에는 더 큰쪽 값을 넣으면 된다.사실 생각해보면 쉽다. arr[i]값과 최대값 + arr[i] 중에 더 큰놈만 dp[i]에 넣는다. 항상 현 상태를 고려해서 최선의 값만 들어간다고 볼 수 있다. 

 

2번 경우를 다시 한번 보자. 만약 arr[i]를 선택하지 않으면 dp[i]에는 무엇을 넣어야 할까..생각해보자. 위에서 arr[i]를 넣는다고 했는데 왜 arr[i]를 넣어야 할까 ? 곰곰히 생각해보자...

 

분명 dp[i]에는 i번째의 연속합의 최대값을 넣어야 하는데..arr[i]를 선택하지 않았다. 그럼 어찌됐든 "연속"이 끊겼기 때문에 0을 넣어야 하나..? 만약 0을 넣으면 i+1에서 검사할 때 arr[i]번째 값을 사용할 수 없게 된다. 분면 "연속"이 끊기긴 했지만 "연속"을 i번째 부터 다시 시작할 수 있다. 

 

그렇기 때문에 2번의 경우는 i번째 이후에 i번 값을 사용하기 위해서 dp[i] = arr[i]를 넣어주는 것이다. i번째에 흐름이 끊기긴 했어도 i번째부터 다시 시작하면 된다.

#include <iostream>
#include <algorithm>

using namespace std;

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

    int arr[100001];
    int dp[100001];

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

    int temp = 0;

    dp[1] = arr[1];
    int result = dp[1];

    for (int i = 2; i <= n; i++)
    {
        dp[i] = max(dp[i - 1] + arr[i], arr[i]);
        result = max(result, dp[i]);
    }

    cout << result;
    return 0;
}