[swexpert] 3307. 최장 증가 부분 수열 (java, D3)

n이 작아서 가능한 이중 포문 방법이다. 

현재 수보다 이전 인덱스에 작은 수가 있으면 그 수에서의 최대 길이+1과 자기 자신의 길이 중 가장 긴 것이 현재 위치에서 가장 긴 길이이다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Solution {
	
	static int t;
	static int n;
	static int[] arr;
	static int[] len;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		t=Integer.parseInt(br.readLine());
		for (int tc = 0; tc < t; tc++) {
			n=Integer.parseInt(br.readLine());
			arr=new int[n];
			len=new int[n];
			Arrays.fill(len, 1);
			st=new StringTokenizer(br.readLine());
			for (int i = 0; i < n; i++) {
				arr[i]=Integer.parseInt(st.nextToken());
			}
			int max=-1;
			for (int i = 1; i < n; i++) {
				for (int j = 0; j <i; j++) {
					if(arr[j]<arr[i] && len[i]<len[j]+1) {
						len[i]=len[j]+1;
					}
				}
				if(max<len[i])max=len[i];
			}
			
			System.out.printf("#%d %d\n",tc+1,max);
		}
		
	}
}