[백준] [최장 증가 부분 수열] 11053. 가장 긴 증가하는 부분 수열

11053. 가장 긴 증가하는 부분 수열

11053번: 가장 긴 증가하는 부분 수열

 

• 내 풀이

n=int(input())
lst=list(map(int,input().split()))
LIS=[0]*n

result=0
for i in range(0,n):
    LIS[i]=1
    for j in range(0,i):
        if lst[j]<lst[i] and LIS[i]<LIS[j]+1:
            LIS[i]=LIS[j]+1
    result=max(result, LIS[i])

print(result)

 

자바 코드

package dp;

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

public class SW3307_ParkSomin {
    static int n;
    static int[] lst,LIS;
    public static void main(String[] args) throws IOException {
        BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st= new StringTokenizer(br.readLine());

        int T= Integer.parseInt(st.nextToken());

        for (int tc = 1; tc <= T; tc++) {
            st=new StringTokenizer(br.readLine());
            n=Integer.parseInt(st.nextToken());

            lst=new int[n];
            LIS= new int[n];

            st=new StringTokenizer(br.readLine());
            for (int i = 0; i < n; i++) {
                lst[i]= Integer.parseInt(st.nextToken());
            }

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

            System.out.printf("#%d %d",tc, max);
            System.out.println();
        }
    }
}