알고스팟 자바(java) 해답 : LIS

import java.util.*;

public class Main{
	static int[] cache;
	static int[] map;
	static int n;
	public static void main(String args[]) throws Exception {
		int testcase;
		int result;
		
		cache = new int[501];
		map = new int[501];
		
        Scanner scanner = new Scanner(System.in);
        testcase = scanner.nextInt();
        
        for(int i = 0; i < testcase; i++){	
        	
        	result = 0;
        	
        	Arrays.fill(cache,-1);
        	
        	n = scanner.nextInt();
        	
        	for(int j = 1; j <= n; j++)
        		map[j] = scanner.nextInt();
        	
        	
        	for(int k = 1; k < n; k++){
        		
        		result = Math.max(result, search(k+1, k));
        		
        	}
        	
       
        	System.out.println(result);
        	
        }
    }
	static int search(int now, int pre){
		
		int temp = 0;
		
		if(cache[pre] != -1)
			return cache[pre];
		
		if(now == n + 1)
			return 1;
		
		for(int i = now; i <= n; i++){
			
			if(map[pre] < map[i]){
				temp = Math.max(temp, search(i + 1, i));
			}
			
		}
		
		temp += 1;
		
		cache[pre] = temp;
		
		return cache[pre];
		
	}
}