[백준/c++] BOJ 1912 - 연속합

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

1912번: 연속합

 

문제 설명

n개의 정수로 이루어진 임의의 수열이 주어진다. 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구한다. 

해결

dp[n] : n번까지의 연속합의 최대합

 

dp[1] = arr[1]

dp[2] = arr[2] + dp[1] || arr[2[

...

dp[n] = dp[n - 1] + arr[n] || arr[n]

 

=> n - 1번까지의 최댓값 + n번값 or n번 값 중 큰 것

 

코드

#include<bits/stdc++.h>
#define x first
#define y second
#define INF 1e9
using namespace std;

int n, answer = 0;
int arr[100001];
int dp[100001];
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> arr[i];

    dp[0] = arr[0]; answer = arr[0];

    for (int i = 1; i < n; i++) {
        dp[i] = max(arr[i], dp[i - 1] + arr[i]);
        answer = max(dp[i], answer);
    }

    cout << answer;
}