[백준 / 실버2] 11053 가장 긴 증가하는 부분 수열 (Java)

문제 보기

사용한 것

• 점차적으로 증가하는 수열 중 가장 긴 크기를 구하기 위한 bottom-up

풀이 방법

• 0 ~ (N - 1) 까지 for loop 돌면서 -> i
• arr[i] 에 입력 값 저장, dp[i]에 1 저장
• (i - 1) ~ 0 까지 감소하는 for loop 돌면서 -> j
• arr[i] > arr[j] 이면 dp[i]를 자신과 dp[j] + 1 중 큰 값으로 교체

코드

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());
        String[] line = br.readLine().split(" ");

        int[] arr = new int[N];
        int[] dp = new int[N];
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(line[i]);
            dp[i] = 1;
            for (int j = i - 1; j >= 0; j--) {
                if (arr[i] > arr[j]) {
                    dp[i] = Math.max(dp[j] + 1, dp[i]);
                }
            }
        }

        int max = IntStream.of(dp)
            .max()
            .orElse(-1);

        System.out.println(max);
    }
}