BOJ) 가장 긴 증가하는 부분 수열 (LIS, Longest Increasing Subsequence)

가장 긴 증가하는 부분 수열

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

풀이

 

어제 푼 가장 큰 증가하는 부분수열 (BIS)와 유사한 문제다.

다른 점이 있다면, 최대 값을 구하는 것이 아니라 최대 길이를 구하는 것이다.

그래서, Math.max를 통해 값을 증가 시켰던 것과 달리, Math.max를 통해 카운트를 증가시켜준다.

 

먼저, 자신만 존재하는 부분 수열에 대해서 dp[n]에 1을 저장한다.

이후, 탐색을 통해 자신보다 큰 숫자 뒤에 존재하면 현재 위치의 dp값에 1을 증가시킨 수 (dp[i] +1)와 해당 숫자의 위치에 있는 dp값 dp[j]의 최대값을 저장한다.

각 탐색이 끝날 때 마다, answer에 최대값을 최신화하면서 답을 구했다.

 

코드

 

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        int[] numArr = new int[n];

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

        br.close();
        solution(n, numArr);
    }

    private static void solution(int n, int[] numArr) {
        int[] dp = new int[n];
        int answer =0;
        for(int i=0; i<numArr.length; i++) dp[i] = 1;

        for(int i=0; i<numArr.length; i++) {
            for(int j=i+1; j<numArr.length; j++) {
                if(numArr[i] <numArr[j])  dp[j] = Math.max(dp[j], dp[i]+1);
            }
            answer = Math.max(dp[i],answer);
        }

        System.out.println(answer);
    }
}