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

Solution

• dp[i] : i 값을 포함하는 최장 증가 부분 수열의 길이
• 각 배열 값들을 보면서 이전까지 이어져온 최장 증가 부분 수열(A)의 마지막 값(=min)보다 크거나 같으면 해당 값을 최장 증가 부분 수열에 추가
• 만약에 마지막 값보다 작다면 해당 인덱스의 앞부터 보면서 해당 값보다 작거나 같고 dp 값이 가장 큰 최장 증가 부분 수열(B)에 추가
• 현재 최장 증가 부분 수열(A)보다 새롭게 값을 추가한 최장 증가 부분 수열(B)의 길이가 더 길어진다면, 최장 증가 부분 수열을 B로 교체

Code

import java.util.*;
class Solution
{
	public static void main(String args[]) throws Exception
	{
		Scanner sc = new Scanner(System.in);
        StringBuffer sb = new StringBuffer();

        int T = Integer.parseInt(sc.nextLine());
        for(int tc=1; tc<=T; tc++){
            sb.append("#").append(tc).append(" ");

            int N = sc.nextInt();

            int array[] = new int[N];
            for(int i=0; i<N; i++){
                array[i] = sc.nextInt();
            }

            int dp[] = new int[N];
            int min = 0;
            int len = 0;

            for(int i=0; i<N; i++){
                if(array[i] >= min){
                    len++;
                    min = array[i];
                    dp[i] = len;
                }else {
                    int index = 0;
                    int max = 0;
                    for (int j = i - 1; j >= 0; j--) {
                        if (array[j] <= array[i]) {
                            if (max < dp[j]) {
                                max = dp[j];
                                index = j;
                            }
                        }
                    }
                    dp[i] = max + 1;
                    if(len < dp[i]){
                        len = dp[i];
                        min = array[i];
                    }
                }


            }
            sb.append(len).append("\n");

        }
        System.out.println(sb);

    }
}