[문제] SWEA 3307번 최장 증가 부분 수열

swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWBOKg-a6l0DFAWr&categoryId=AWBOKg-a6l0DFAWr&categoryType=CODE&problemTitle=3307&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1

SW Expert Academy

내 풀이

 

LIS 알고리즘

 

public class SWEA_3307 {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(in.readLine());
		StringBuilder sb = new StringBuilder();

		for (int tc = 1; tc <= T; tc++) {
			int N = Integer.parseInt(in.readLine());
			int[] num = new int[N];
			StringTokenizer st = new StringTokenizer(in.readLine()," ");
			for(int i=0;i<N;i++) {
				num[i] = Integer.parseInt(st.nextToken());
			}
			
			int[] LIS = new int[N];	// 동적 배열: 각원소를 마지막에 끼워넣었을 때 최장 증가 길이
			int max = 0;
			
			for(int i=0;i<N;i++) {
				LIS[i] = 1;		// 자기 혼자 있는 수열 ->최장길이: 1
				
				for(int j=0;j<i;j++) {	// i번째 원소보다 작은 j에 대해
					// i번쨰 원소가 j번쨰 원소보다 커야 끼워넣을 수 있음 && j번째 원소길이+1가 현재 최장길이 보다 크면 갱신
					if(num[i]> num[j] && LIS[i] < LIS[j]+1) {
						LIS[i] = LIS[j]+1;
					}
				}
				if(max<LIS[i])
					max = LIS[i];
			}
			sb.append("#").append(tc).append(" ").append(max).append("\n");
		}
		System.out.println(sb);
	}

}