[Java]BOJ 11053 : 가장 긴 증가하는 부분 수

https://www.acmicpc.net/problem/11053

🚩문제

🔓문제해결(dp)

1. 수열의 크기 N을 입력받는다.

2. 수열을 입력받는다.

3. dp에는 본인 포함 및 본인보다 작은 원소를 넣는다.

3-1. 자기 자신을 먼저 넣고 시작한다 dp[i]=1

3-2. 이전값보다 자신이 더 크면 이전까지 계산된 길이에 +1을 해주고, 현재 자신이 가진길이와 +1 된 길이중 더 큰 값을

자기 자신의 길이로 가진다

4. 이전값과 비교하는 반복문이 종료되면 최대값을 결과값에 저장해준다.

5. 최종적으로 for문이 끝나면 결과값을 출력한다

import java.io.*;

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 [] str = br.readLine().split(" ");
        int [] arr = new int[n]; //수열
        int [] dp = new int[n]; // 부분 수열 최대 길이
        int result =0;

        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(str[i]);
            dp[i] = 1; // 자기자신
            for (int j = 0; j < i; j++) {
                if (arr[i] > arr[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            result = Math.max(result, dp[i]);
        }
        System.out.println(result);

    }

}