백준 11053 (가장 긴 증가하는 부분 수열) - java

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

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

해당 문제의 경우 DP 배열의 값들을 전부 1로 초기화해준다. 그 이유는 해당 값으로만 이루어진 수열의 길이가 1이기 때문이다

2부터 n 즉 2번째 수부터 끝까지를 검사해가며 1부터 n-1까지의 수로 시작하는 부분 수열의 최대 길이를 갱신해준다

 

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

public class Main {
    static int n= 0;
    static int[] arr = new int[1001];
    static int[] dp = new int[1001];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        for(int i=1;i<=n;i++)
        {
            arr[i] = Integer.parseInt(st.nextToken());
            dp[i] =1; // 모든 좌표의 값을 1로 초기화 (해당 수로만 이루어진 부분 수열의 길이)
        }
        int max = 1;
        for(int i=2;i<=n;i++)
        {
            for(int j=1;j<i;j++) {
                if (arr[j] < arr[i]&&dp[i]<dp[j]+1) // 증가하는 수열이며 dp[i] 가 갱신 될 수 있는 경우
                {
                    dp[i] = dp[j]+1; // 길이를 증가
                    max = Math.max(max,dp[i]); // 최댓값 갱신
                }
            }
        }
        System.out.println(max);
        br.close();
    }
}