[백준] 1912번 연속합 (C++) - dynamic programming

문제

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

1912번: 연속합

코드

#include <iostream>

using namespace std;

int dp[100001] = {-1001,};

int main(){
  int n;
  cin >> n;
  int result = -1001;
  for(int i=1; i<=n; i++){
    int a;
    cin >> a;

    if(i == 1 || a > a+dp[i-1]){
      dp[i] = a;
    }
    else{
      dp[i] = a+dp[i-1];
    }

    if(dp[i] > result){
      result = dp[i];
    }
  }
  cout << result;
  return 0;
}

정리

지금까지 dynamic programming 문제를 풀면서 dp배열에 마지막(dp[n])이 답이 되어야 한다는 생각을 가지고 있었다. 그래서 이 문제를 처음 풀 때도 어떻게 dp배열에 마지막이 연속합의 최댓값이 될 수 있을까를 생각해서 풀었는데 쉽지 않았다. 그래서 다른 사람들의 풀이를 봤더니 dp배열의 최댓값들을 다른 변수에 저장해 놓고 푸는 것을 확인할 수 있었다. 이 문제를 이후로 dp문제를 풀 때 더 넓은 관점에서 바라봐야겠다.

참조

https://luv-n-interest.tistory.com/919

https://mtoc.tistory.com/41