[SWEA]최장 증가 부분 수열(3307번, 자바), DP

 

import java.util.*;

class Solution
{

	static String answer;
	static int N,M,K;
	static int[] d;
	static int[] dp;
	
	public static void main(String args[]) throws Exception
	{
		
		Scanner sc=new Scanner(System.in);
		int T=sc.nextInt();
		
		
		for(int test_case = 1; test_case <= T; test_case++)
		{
			N=sc.nextInt();
			d=new int[N];
			dp=new int[N];
			
			for(int i=0;i<N;i++) {
				d[i]=sc.nextInt();
			}
			int max=0;
			Arrays.fill(dp, 1);
			
			for(int i=0;i<N;i++) {
				for(int j=i+1;j<N;j++) {
					if(d[i]<d[j]) {
						dp[j]=Math.max(dp[j],dp[i]+1);
						max=Math.max(dp[j], max);
					}
				}
			}
			
			System.out.println("#"+test_case+" "+max);
		}
	}
}