BOJ 1912번 연속합

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

GitHub : https://github.com/junho0956/Algorithm/blob/master/1912/1912/%EC%86%8C%EC%8A%A4.cpp

 

연속 수열로 부분 합을 만들어가려면

당장 현재 값이 더 커서 현재값만 넣거나

현재값에 이전값들의 합만 넣거나 둘중 하나가 된다.

 

=> dp[i] = max(arr[i], dp[i-1]+arr[i])

 

#include <iostream>
#include <algorithm>
using namespace std;
 
int dp[100001];
int arr[100001];
int n;
 
int main() {
    ios::sync_with_stdio(false);
 
    cin >> n;
    for (int i = 0; i < n; i++) cin >> arr[i];
 
    int Max;
    Max = dp[0] = arr[0];
 
    for (int i = 1; i < n; i++) {
        dp[i] = max(arr[i], arr[i] + dp[i - 1]);
        Max = max(Max, dp[i]);
    }
    cout << Max;
 
    return 0;
}