[C++] 백준 11053번 가장 긴 증가하는 부분 수열

 

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

 

수열 A에서 가장 길게 증가하는 수열을 구하는 문제입니다.

1. 차례대로 검색

2. 전에 수열이 현재 수열보다 길면서 && 전의 값이 현재값보다 작으면 

3. 현재수열에 전 수열의 길이 +1을 DP에 저장

 

for (int i = 1; i < n; ++i) {
 	for (int j = i - 1; j >= 0; --j) {
 		if (memo[i] <= memo[j] && num[i] > num[j]) {  
 			memo[i] = memo[j] + 1;
 		}
 	}
}

 

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

int maxNum = -987654321;
int num[1010];
int memo[1010];

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

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

   return 0;
}