[백준] 문제번호 1463 (가장 긴 증가하는 부분 수열)(java)

[문제]

 

[답안]

import java.util.Scanner;

public class Main {
    public static void main(String args[]) {

        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt(); // 수열의 크기 N
        int [] arr = new int[n]; // 수열을 이루고 있는 배열 arr

        int [] dp = new int[n + 1]; // dp 테이블 만들기

        int result = 0; //비교를 위한 값

        for (int i = 0; i < n; i++) { // 수열의 크기만큼 돌면서
            arr[i] = sc.nextInt(); // 배열에 담아주고
        }

        for (int i = 1; i <= n; i++) {
                 dp[i] = 1;
            for (int j = 1; j < i; j++) {
                if (arr[j - 1] < arr[i - 1]){ // 이전값이 다음값보다 작으면(부분수열이 증가되고 있으면)
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            result = Math.max(result, dp[i]);
        }
        System.out.println(result);
    }
}

* dp 이용문제