[C/C++] 백준 1912번

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

 

굿모닝.

오늘 풀어볼 문제는 백준 1912번, 실버2 문제이다.

 

n개의 정수로 이루어진 임의의 수열이 주어질 때, 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하는 프로그램을 만든다.

 

 

조건

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

 

 

아이디어

• dp[i]: i번째 수를 포함하는 연속된 부분합의 최댓값.
• dp[1]=num[1]: 첫 번째 수는 그대로 선택.
• 점화식
  • dp[i]=max(dp[i−1]+num[i],num[i])

 

 

 

코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

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

    int N;
    cin>>N;

    vector<int> num(N + 1, 0);
    vector<int> dp(N + 1, 0);

    //input and initialization
    for(int i=1; i<=N; i++){
        cin >> num[i];
    }
    
    dp[1] = num[1];
    int maxSum = dp[1];

    // dynamic programming
    for(int i=2; i<=N; i++) {
        dp[i] = max(dp[i-1]+num[i], num[i]);
        maxSum = max(maxSum, dp[i]); // 최대값 업데이트
    }
    
    // 결과 출력
    cout << maxSum << "\n";
    
    return 0;
}