백준 - 11053번

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

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

문제 풀이

 

기본 길이가 1이므로 모든 dp 배열을 1로 초기화 한다음 arr[i] > arr[j]일때

 점화식 dp[i] = max(dp[i], dp[j]+1)을 통해 i 배열이 j 배열보다 크다며 dp 값을 1 증가시키고

dp 배열에서 가장 큰 값을 출력함으로써 가장 긴 길이를 출현한다.

import java.util.Scanner;
 
public class Beak11053 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
 
        int n = sc.nextInt();
        int arr[] = new int[n + 1];
        int d[] = new int[n + 1];
 
        d[1] = 1;
 
        for (int i = 1; i <= n; i++)
            arr[i] = sc.nextInt();
 
        for (int i = 2; i <= n; i++) {
            d[i] = 1;
            for (int j = 1; j < i; j++) {
                if (arr[i] > arr[j] && d[i] <= d[j])
                    d[i] = d[j] + 1;
                else if (arr[i] == arr[j])
                    d[i] = d[j];
            }
        }
 
        int max = 0;
        for (int i = 1; i <= n; i++)
            max = Math.max(d[i], max);
 
        System.out.println(max);
 
        sc.close();
    }
}