[백준] 1912번: 연속합

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

문제

알고리즘 접근 방법

DP 를 이용한다.

수열이 담긴 배열 a 와 최대합을 저장하는 배열 dp 가 있다.

N번째 수를 선택한다는 가정 하에

1. 연속일 때 -> dp[N-1] + a[i]
2. 연속이 아닐 때 -> a[i]

이 둘을 비교하여 더 큰 값이 dp[n] 이다.

결과는 dp[n] 중에 제일 큰 값을 출력하면 된다.

풀이

#include <iostream>
#include <algorithm>

 using namespace std;

 int main(){

    int n;

    cin >> n;

    int a[n+1] = {0, };
    for (int i=1; i<=n; i++)
        cin >> a[i];

    int dp[n+1] = {0, };

    dp[1] = a[1];

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

    int result = dp[1];
    for(int i=2; i<=n; i++)
    {
        if(result < dp[i])
            result = dp[i];
    }

    cout << result << endl;

    return 0;
 }

정리

이것도 생각이 꼬였는데 알고 보면 쉬운 문제였당 .!

💡 참고 포스팅

mtoc님 블로그