[SW expert Academy] SWEA 3307번 최장 증가 부분 수열 자바(Java)

[D3] 최장 증가 부분 수열 - 3307

문제 링크

성능 요약

메모리: 36,952 KB, 시간: 219 ms, 코드길이: 799 Bytes

제출 일자

2023-10-29 23:47

출처: SW Expert Academy, https://swexpertacademy.com/main/code/problem/problemList.do

import java.util.Scanner;
class Solution
{
	public static void main(String args[]) throws Exception {
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for(int tc = 1; tc <= T; tc++)
		{
            int n = sc.nextInt();
            int[][] dp = new int[n+1][2];
            int result = 0;
            for(int i = 1; i <= n; i++){
                dp[i][0] = sc.nextInt();
            }
            for(int i = 1; i <=n; i++){
                int maxIdx = 0;
                for(int j = 0; j < i; j++){
                    if(dp[i][0] > dp[j][0] && dp[j][1] > dp[maxIdx][1]) maxIdx = j;
                }
                dp[i][1] = dp[maxIdx][1] + 1;
                result = Math.max(dp[i][1] , result);
            }
            System.out.println("#" + tc + " " + result);
		}
	}
}