[백준 1912] 연속합

0. 제목

• 백준 1912 연속합
• BOJ 1912 연속합
• C++ 1912 연속합

---

1. 문제

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

---

2. 풀이

• DP 방식을 이용하였다.
• 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하는 것이 목적이다.
• 예를 들어, 배열의 값들이 10, 20, -100, -500, 700, 30  이라고 할 때, dp[1] = 10, dp[2] = 30, dp[3] = -70, dp[4] = -500, dp[5] = 700, dp[6] = 730 이다.
• 이 배열 dp 의 원소 값들을 구하는 규칙은 다음과 같다.
• 만약 dp[i]를 구하려고 할 때 dp[i-1] 가 음수라면 dp[i] = arr[i] 로 업데이트 해주고 양수라면 dp[i] = dp[i-1] + arr[i] 를 해주면 된다.
• 그렇게 되면 dp[i] 는 arr[i] 를 포함한 가장 큰 합이 될 것이다.
• 중요한 부분은 바로 다음 부분이다.
• 앞서 구한 배열 dp의 원소값들 중 최댓값을 구해야 한다. 그것이 문제에서 요구하는 것이다.

---

3. 코드

 

#include <iostream>
using namespace std;
 
int main(int argc, const char * argv[]) {
    int n;
    int arr[100001];
    int dp[100001];//dp[i] 에는 arr[i] 를 포함하였을때의 최대 합을 담는다.
    int max;
    
    
    cin >> n;
    for(int i = 1;i <= n; i++){
        cin >> arr[i];
    }
    
    //max 로도 구현 가능
    dp[1] = arr[1];
    max = dp[1];
    for(int i = 2; i <= n; i++){
        if(dp[i-1] + arr[i] > arr[i]) //if(dp[i-1]) > 0)
            dp[i] = dp[i-1] + arr[i];
        else
            dp[i] = arr[i];
    }
    
    //이 부분부터가 핵심
    max = dp[1];
    for(int i = 2; i <= n; i++){
        if(max < dp[i])
        max = dp[i];
    }
    //cout << dp[4]; 1, 2, 3, -100 일때 dp[4] = -96 이다. dp가 정답이 아니라 dp들을 비교하여 최대 값이 정답이다.
    cout << max << '\n';
    
    return 0;
}