백준 1912 / 연속합

다이나믹 프로그래밍 연습문제.

어렵다.

생각해내기가 어렵다.

머리를 싸매고 여며봤는데 생각이 안나 결국 해결방법을 찾아보았다.

방법은 이러하다.

입력된 배열 말고 다른 배열을 하나 만든다 (D 배열이라 가정)

D배열엔 그 인덱스까지 더한 최대값을 적어놓는다.

예)

그리고 D 배열에 들어있는 성분 중 가장 큰 수를 출력한다.

코드

#include <stdio.h>
#include<iostream>
#include <algorithm>
using namespace std;
 
 
int arr[100001];
int d[100001];
 
int main() {
 
    int n;
    cin >> n;
 
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
        
    }
 
    d[0] = arr[0];
    for (int i = 1; i < n; i++) {
 
        if (d[i - 1] + arr[i] > arr[i]) {
            d[i] = d[i - 1] + arr[i];
        }
        if (d[i - 1] + arr[i] <= arr[i]) {
            d[i] = arr[i];
        }
 
    }
 
    int ans = -2000000000;
 
    for (int i = 0; i < n; i++) {
        ans = max(ans, d[i]);
    }
 
    cout << ans;
}

머리 아프다. 저녁먹으러 가야지