백준 13398 연속합 2 / C++

문제 : 13398

풀이 point

값을 지운 dp 배열과 값을 안지운 dp배열 두개를 통해 최대값을 갱신해나간다.

dp[i][0] = std::max(arr[i], arr[i]+dp[i-1][0])
dp[i][1] = std::max(dp[i-1][0], arr[i]+dp[i-1][1])

점화식은 이런 형태이다.

풀이 방법

dp[i][0]은 값을 지우진 않은 dp 배열, dp[i][1]은 값을 지운 배열이다.
dp[i][0]은 값을 지우지 않은 배열이기 때문에 지우지 않은 배열과 비교하여 가장 최대값을 갱신한다.
dp[i][1]은 값을 지우지 않은 배열과 지운 배열 + arr[i]와 최대를 비교한다.

코드

//백준 13398, 연속합 2

#include <iostream>

int arr[100'005];
int dp[100'005][2];

int main (){
    
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    std::cout.tie(NULL);

    int N;

    std::cin >> N;

    for(int i{0}; i<N; ++i){
        std::cin >> arr[i];
    }
    dp[0][0] = arr[0]; //0은 안지움
    dp[0][1] = arr[0];

    int max = arr[0];
    
    for(int i{1}; i<N; ++i){
        dp[i][0] = std::max(arr[i], arr[i]+dp[i-1][0]);
        dp[i][1] = std::max(dp[i-1][0], arr[i]+dp[i-1][1]);
        max = std::max(max, std::max(dp[i][0], dp[i][1]));
    }

    std::cout << max;



    return 0;
}