[C++] 백준 1912번 : 연속합 (S2)

#문제

www.acmicpc.net/problem/1912

1912번: 연속합

 

#풀이 & 학습한 내용

p[i]는 i번째 원소를 입력받은 배열이고, dp[i]를 "i번째 원소를 마지막으로 하는 연속합의 최댓값"이라 정의하자. 이때 dp[i-1]이 양수라면 dp[i]는 dp[i-1]+p[i]이고, dp[i]가 음수라면 dp[i]는 p[i]가 된다. 이를 이용하여 for문을 구성해 dp배열을 모두 채우고, 최댓값은 dp배열 값들중에 하나이므로 반복문을 통해 최댓값을 구한다.

 

#소스코드

#include<iostream>
#include<algorithm>
 
using namespace std;
 
int dp[100002];
int p[100002];
 
int main(void) {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> p[i];
    }
 
    dp[0] = p[0];
    for (int i = 1; i < n; i++) {
        if (dp[i - 1] > 0)
            dp[i] = dp[i - 1] + p[i];
        else
            dp[i] = p[i];
    }
 
    int max = dp[0];
    for (int i = 1; i < n; i++) {
        if (max < dp[i])
            max = dp[i];
    }
    cout << max << '\n';
}

 

github.com/HoYoungChun/BOJ_algorithm/blob/master/Dynamic_Programming/BOJ_1912.cpp

HoYoungChun/BOJ_algorithm