[백준][1912번][DP] 연속합

연속합

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

<코드>

#include <stdio.h>
 
int main(void){
 
    int N;
    int number[100010] = {};
    int Dp[100010] = {};
    int max;
    scanf("%d", &N);
 
    for (int i = 1; i <= N; i++)
        scanf("%d", &number[i]);
 
    for (int i = 1; i <= N; i++)
    {
        
        if (Dp[i - 1] + number[i] > number[i]){
            Dp[i] = Dp[i - 1] + number[i];
        }
        else
        {
            Dp[i] = number[i];
        }
    
    }
    max = Dp[1];
    for (int i = 2; i <= N; i++)
            if (max < Dp[i])
                max = Dp[i];
 
    printf("%d\n", max);
}

<문제 푼 요령>

1. 이 문제는 최대값을 구하기 위해서는 현재의 자신의 값을 선택하는 경우의 수가 두가지이다.

2. 첫 번째 경우는 이전의 값을 더한것과 지금의 값을 더한 값이 최대일 때랑 이전의 값을 더하지 않고 현재의 값만이 최대일 때 이 두가지 경우만 따지면 된다.