Beakjoon 1912 연속합

14 Feb 2021 in Algorithm

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

나의 풀이

DP[i] = i번에서 연속된 수의 가장 큰 합
DP[i] = max(DP[i-1] + arr[i], arr[i])
예를 들어 수열 A = {2 1 -4 3 4 -4 6 5 -5 1}일 때
DP[0] = A[0] = 2
DP[1] = max(DP[0] + A[1], A[1]) = max(2+1, 1) = 3
DP[2] = max(DP[1] + A[2], A[2]) = max(3-4, -4) = -1
DP[3] = max(DP[2] + A[3], A[3]) = max(-1+3, 3) = 3
DP[4] = max(DP[3] + A[4], A[4]) = max(3+4, 4) = 7
… DP[9] = max(DP[8] + A[9], A[9]) = max(9+1, 1) = 10
위에서 구한 DP의 최대값이 연속된 수의 합 중 가장 큰 합이다.

풀이 코드 : 1912 연속합

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

int DP[100000];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int N, num;
    vector<int> arr;
    cin>>N;
    for(int i=0;i<N;i++){
        cin>>num;
        arr.push_back(num);
    }

    int answer = arr[0];
    DP[0] = arr[0];
    for(int i=1;i<N;i++){
        DP[i] = max(DP[i-1] + arr[i], arr[i]);
        if(DP[i] > answer) answer = DP[i];
    }
    cout<<answer;
}

채점결과