백준 #1912. 연속합

백준 #1912. 연속합

정리

• 이 문제도 다이나믹 프로그래밍 기법으로 해결할 수 있는 문제이다.

• bottom-up 방식으로, 연속합의 최댓값을 비교해서 저장해 두고, 계속 수열을 비교해 나가면서 기존의 연속합의 최댓값과, 새로운 연속합의 값을 비교해 나가는 방식으로 문제를 해결했다.

• 수열의 숫자는 -1000보다 크거나 같고, 1000보다 같거나 작은 정수이다. 즉, 수열에 음수가 포함될 수 있다. 따라서 각 숫자가 양수인지 음수인지에 따라서 다르게 처리해줘야 한다. 자세한 내용은 아래 코드에 주석으로 적어 뒀으니 참고하면 좋을 듯하다.
  
  

정답 코드

#include <iostream>
#include <algorithm>

using namespace std;

int main(void) {
    int n;
    int arr[100001];
    int dp[100001];
    // dp[]에는 각 인덱스에서의 연속합을 더해 갖고 있는 역할을 한다.
    int res;
    // res 변수에는 가장 큰 연속값을 저장해 두고, 최종적으로 답을 출력하는 역할을 한다.
    
    cin>>n;
    for(int i=1; i<=n; i++) {
        cin>>arr[i];
    }
    
    if (arr[1] >= 0) dp[1] = arr[1];
    else dp[1] = 0;
    res = arr[1];
    for(int i=2; i<=n; i++) {
        if (arr[i] >= 0) {
            // i번째 숫자가 양수인 경우, dp[]에 arr[i]를 더해준 것을 연속합으로 저장한다.
            dp[i] = dp[i-1] + arr[i];
            res = max(res, dp[i]);
        }
        else {
            // i번째 숫자가 음수인 경우, 두 가지 case가 가능하다.
            if (dp[i-1] + arr[i] >= 0) {
                // 기존 연속합 + 이번 음수 >= 0일 경우, 그대로 더해 연속합으로 저장해 둔다.
                dp[i] = dp[i-1] + arr[i];
                res = max(res, dp[i]);
            }
            else {
                // 기존 연속합 + 이번 음수 < 0일 경우, 이번 숫자를 더하면 연속합이 최대가 될 가능성은 없다.
                dp[i] = 0;
                res = max(res, arr[i]);
            }
        }
    }
    
    cout<<res<<endl;
    return 0;
}