[LIS] 최대 증가 부분 수열

[LIS] 최대 증가 부분 수열 : https://algospot.com/judge/problem/read/LIS

< 소스코드 >

lis(s) : s 번째 요소에서 시작하는 최대 증가 부분 수열

#include <stdio.h>
 
int n;
int a[501], d[501];
 
int max(int a, int b)
{
    return a > b ? a : b;
}
 
int lis(int s)
{
    int ret = 0;
    if(s == n-1) return 1;
    if(d[s]) return d[s];
    for(int i=s+1; i<n; i++) {
        if(a[s] < a[i])
            ret = max(ret, lis(i)); 
    }
    return d[s] = ret+1; 
}
 
int main()
{
    int tc;
    scanf("%d", &tc);
 
    while(tc--) {
        int ans=0;
        scanf("%d", &n);
 
        for(int i=0; i<n; i++) {
            scanf("%d", a+i);
            d[i] = 0;
        }
        for(int i=0; i<n; i++)
            ans = max(ans, lis(i));
        printf("%d\n", ans);
    }
 
    return 0;
}

>> 36-37 : 이부분에서 주의해야 한다. printf("%d\n", lis(0)); 으로만 제출해서 두번이나 틀렸다.

>> 0번째 요소에서 시작하는 최대 증가 부분수열이 항상 제일 길지는 않다. 반례 : 9 1 2 3 4 >> 정답은 4인데, 위와 같이 안하면 1이나온다.

- 위 코드는 길이만 출력하는 코드이다.

>> 부분 수열을 이루는 수열도 출력하고 싶다면..? http://ychooni.tistory.com/163