[C++] 백준 1912번 연속합

 

다이나믹 프로그래밍 문제입니다.

 

n개의 정수에서 연속된 몇개의 숫자를 골라서 최대값을 만들어내는 문제입니다.

 

예를들어

-3 1 3 5 -3 4 -21 이라는 수열이 있다면

1 + 3 + 5 + -3 + 4 = 10이 답이됩니다.

 

문제는

memo[i] = max(memo[i-1] + num[i], num[i])

를 이용해서 문제를 풀었습니다.

1. 이전값과 현재값을 더한값

2. 현재 값

을 비교해서 큰것을 memo에 넣어둡니다.

그리고 다음 번을 확인할때 넣었던 memo값은 memo[i-1]가 됩니다. 현재값은 num[i].

memo[i-1] + num[i]와 num[i]를 비교해서 큰것을 memo에 저장합니다.

이를 반복해서 문제를 해결합니다.

 

#include <iostream>
#include <algorithm>
using namespace std;

int memo[100010];
int num[100010];
void init()
{
   for (int i = 0; i < 10010; ++i) {
      num[i] = 0;
      memo[i] = 0;
   }
}

int main(int argc, char *argv[])
{
   init();
   int n;
   int maxNum = -987654321;
   
   cin >> n;
   for (int i = 0; i < n; ++i) {
      cin >> num[i];
   }
   memo[0] = num[0];
   for (int i = 1; i < n; ++i) {
      memo[i] = max(memo[i - 1] + num[i], num[i]);
   }
   for (int i = 0; i < n; ++i) {
      if (memo[i] > maxNum) {
         maxNum = memo[i];
      }
   }
   cout << maxNum;
   return 0;
}