[백준] DP 1912번: 연속합

문제

n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다.

예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다.

입력

첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.

출력

첫째 줄에 답을 출력한다.

Approach

사용 알고리즘: DP

• 두가지 경우를 비교해서 최댓값을 찾아나가면 된다.

1. 현재 수를 고르는 경우
2. 전에 수랑 현재 수를 둘 다 고르는 경우

• 점화식 --> max(d[i], d[i - 1] + arr[i])

Source Code

#include <iostream>
#include <string>
#include <vector>
#include <bits/stdc++.h>
using namespace std;

int d[100000] = {0,}; // DP 테이블 초기화 

int main()
{
    int n; // n 입력받기
    cin >> n;
    
    vector<int> nums; 
    // 숫자 입력받고 dp 테이블에도 숫자 저장
    for (int i = 0; i < n; i++)
    {
        int num;
        cin >> num;
        nums.push_back(num);
        d[i] = num;
    }
    
    int result = d[0]; // 수가 1개일때는 그 수가 최댓값
    
    // 보텀업 dp 진행
    for (int j = 1; j < n; j++)
    {
        d[j] = max(d[j], d[j - 1] + nums[j]);
        
        if (d[j] > result)
            result = d[j];
    }
    
    cout << result << endl; // 답안 출력
    
    return 0;
}