[SW Expert Academy] 최장 증가 부분 수열 (D3)

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

SW Expert Academy

import java.util.Scanner;

class Solution {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int t = sc.nextInt();
		for (int tc = 1; tc <= t; tc++) {
			int n = sc.nextInt();

			int a[] = new int[n];
			int d[] = new int[n];

			for (int i = 0; i < n; i++) {
				a[i] = sc.nextInt();
			}

			int max = Integer.MIN_VALUE;

			for (int i = 0; i < n; i++) {
				d[i] = 1;
				for (int j = 0; j < i; j++) {
					if (a[j] < a[i]) {
						d[i] = Math.max(d[i], d[j] + 1);
					}
				}
			}

			for (int i = 0; i < n; i++) {
				max = Math.max(max, d[i]);
			}

			System.out.println("#" + tc + " " + max);
		}
	}
}

 

참고

https://www.youtube.com/watch?v=sYh62pujaH8&t=5s