[C++] 백준 1912번 연속합

문제

n개의 수가 주어졌을 때, 연속한 수들의 최댓값을 구한다.
단, 수는 한 개 이상 더해야 한다.

풀이

1) 음수?

처음 접근 할 때는 '최댓값'을 구한다는 것에서 단순히 음수 앞에서 끊어주면 된다고 생각했다.
하지만 음수를 더한 값이 양수인 경우에는 최댓값을 구하기 위해 계속해서 더해줘야 한다.
따라서 음수인 경우에도 끊지 않고 계속해서 더해야 한다.

2) 점화식

그렇다면 끊기는 경우는 언제일까?

n개의 수를 입력받은 배열을 arr이라 통칭하겠다.
n-1번째 까지 구한 최댓값 + arr[n] 을 arr[n]과 비교했을 때, arr[n]이 더 크다면 그전까지 구한 최댓값들을 더해줄 필요가 없으므로 최댓값은 arr[n]이 된다.

따라서 dp[n] = max(dp[n-1] + arr[n], arr[n]) 이 된다.

주의할 점 ✨

수는 한 개 이상 더해야 하므로 처음 최댓값은 arr[0]으로 설정한다.

코드

#include <iostream>
#include <algorithm>
using namespace std;

int main(){
    int n;
    int arr[1000001];
    int dp[1000001];

    cin >> n; // 수의 개수
    
    for (int i = 0; i < n; i++){ // 수열 입력받기
        cin >> arr[i];
        dp[i] = arr[i];
    }

    int ans = arr[0];

    for (int i = 1; i < n; i++){
        dp[i] = max(dp[i], dp[i-1] + arr[i]);
        // (현재 수)와 (이전까지의 최댓값 + 현재 수) 중 더 큰 것을 반환
        ans = max(ans, dp[i]);
        // 가장 큰 수를 반환
    }
    
    cout << ans;
}