백준 1912 (연속합) / C++

문제 링크 : www.acmicpc.net/problem/1912

1912번: 연속합

> 풀이

 

동적 계획법(DP) 문제입니다. 점화식의 기준을 어디에 두냐에 따라 구현방식이 조금 달라질것 같네요.

 

최대값을 구해야 하니 sort를 사용합시다.

#include <bits/stdc++.h>
using namespace std;

int dp[100001];
int arr[100001];
int N;

int main(void) {
        scanf("%d", &N);
        for (int i = 0; i < N; i++) scanf("%d", &arr[i]);

        dp[0] = arr[0];
        for (int i = 1; i < N; i++) {
                dp[i] = max(arr[i], arr[i] + dp[i - 1]);
        }
        
        sort(dp, dp + N);
        printf("%d", dp[N - 1]);
        return 0;
}