3307 최장 증가 부분 수열

https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWBOKg-a6l0DFAWr

d[i] = a[i]를 마지막으로 하는 최장 증가 부분 수열의 최대 길이

자기 자신이 부분 수열이 될 수 있으므로 d 배열의 초기값을 1로 둔다. d[i]은 j=0~i-1까지 보면서 a[j]<a[i] 이면서 d[j]+1>d[i]인 경우 d[i]을 d[j]+1로 갱신한다. O(N^2)으로 테이블을 모두 채울 수 있다.

#include <cstdio>
#include <algorithm>
using namespace std;
 
int t,n,a[1000],d[1000],ans;
 
int main()
{
    scanf("%d",&t);
    for(int k=1;k<=t;k++)
    {
        scanf("%d",&n);
        for(int i=0;i<n;i++)
            scanf("%d",&a[i]);
        fill_n(d,n,1),ans=0;
        for(int i=1;i<n;i++) for(int j=0;j<i;j++)
            if(a[j]<=a[i] && d[i]<d[j]+1)
                d[i]=d[j]+1,ans=max(ans,d[i]);
        printf("#%d %d\n",k,ans);
    }
    return 0;
}