[c언어/c++] Longest Increasing Sequence - LIS 동적계획법

어떤 정수 수열에서 0개 이상의 숫자를 지우면 이 수열의 부분 수열 (subsequence) 를 얻을 수 있다. 예를 들어 10 7 4 9 의 부분 수열에는 7 4 9, 10 4, 10 9 등이 있다. 단, 10 4 7 은 원래 수열의 순서와 다르므로 10 7 4 9 의 부분 수열이 아니다.

어떤 부분 수열이 순증가할 때 이 부분 수열을 증가 부분 수열 (increasing subsequence) 라고 한다. 주어진 수열의 증가 부분 수열 중 가장 긴 것의 길이를 계산하는 프로그램을 작성하라.

어떤 수열의 각 수가 이전의 수보다 클 때, 이 수열을 순증가 한다고 한다.

문제 링크 - https://algospot.com/judge/problem/read/LIS

#include<stdio.h>

#include<memory.h>
#include<algorithm>
#include<vector>
using namespace std;

int n;
int seq[500];
int cache[500];

int lis(int);

int main(){
 
 int loop;
 scanf("%d",&loop);

 for(int c = 0 ; c < loop ; c++){
  int ans = 0;
  memset(seq,0,sizeof(seq));
  memset(cache,-1,sizeof(cache));

  scanf(" %d",&n);
  
  for(int i = 0 ; i < n ; i++){
   scanf(" %d",&seq[i]);
  }
  for(int i = 0 ; i < n ; i++){
   ans = max(ans,lis(i));
  }
  printf("%d\n",ans);
 }

 return 0;

}
int lis(int start){

 if(cache[start] != -1) return cache[start];

 cache[start] = 1;

 for(int next = start + 1 ; next < n ; next++){
  if(seq[start] < seq[next]) {
   cache[start] = max(cache[start],lis(next)+1);
  }
 }

 return cache[start];
}