[C++] 백준 11055번 가장 큰 증가 부분 수열

 

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

 

수열이 주어졌을 때 증가하는 수열 중 합이 가장 큰 것을 구하는 문제입니다.

 

차례대로 검사를 하면서

현재 값이 이전의 값보다 크면

memo에 저장된 값과 이전 memo값 + 현재위치값 중 큰 것을 memo에 저장합니다.

 

코드로 보면 아래와 같습니다.

for (int j = i - 1; j > 0; --j) {
 	if (sequence[i] > sequence[j]) {   
 		memo[i] = max(memo[i], memo[j] + sequence[i]);
 	}
}

 

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

int main(int argc, char *argv[])
{
   int sequence[1010] = { 0, };
   int memo[1010] = { 0, };
   int n;
   int result = 0;
   cin >> n;

   for (int i = 1; i <= n; ++i) {
      cin >> sequence[i];
      memo[i] = sequence[i];
      for (int j = i - 1; j > 0; --j) {
         if (sequence[i] > sequence[j]) {
            memo[i] = max(memo[i], memo[j] + sequence[i]);
         }
      }

   }

   for (int i = 1; i <= n; ++i) {
      result = max(result, memo[i]);
   }

   cout << result << endl;
   return 0;
}