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

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

 

문제 설명

---

문제 풀이

#include<stdio.h>
int num[100001], dp[100001];
int main()
{
    int i, n, max;
    scanf("%d", &n);

    for(i = 0; i < n; i++) {
        scanf("%d", &num[i]);
    }

    max = dp[0] = num[0];

    for(i = 1; i < n; i++) {
        if(dp[i-1] + num[i] > num[i]) dp[i] = dp[i-1] + num[i];
        else dp[i] = num[i];

        if(dp[i] > max) max = dp[i];
    }

    printf("%d", max);

    return 0;
}

현재 수(num[i])와 이전 수의 합을 현재 수와 비교해서 더 큰 수를 dp 배열에 저장(dp[i])해서 연속합을 구해간다.