[백준] 11722 가장 긴 감소하는 부분 수열_Java

📖  문제

---

백준 11722 가장 긴 감소하는 부분 수열

⚠️  주의사항

---

이전 11053에서 if문만 바뀐 형태

2022.05.03 - [[Java] 백준 문제풀이/DP] - [백준] 11053 가장 긴 증가하는 부분 수열_Java

 

✏️  풀이

---

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int max = 1;

        int[] arr = new int[N + 1];
        int[] dp = new int[N + 1];

        for(int i=1; i<=N; i++) arr[i] = sc.nextInt();

        dp[0] = 0;
        dp[1] = 1;

        for (int i = 2; i <= N; i++) {
            dp[i] = 1;

            for (int j = 1; j < i; j++) {
                if (arr[i] < arr[j] && dp[i] == dp[j]) dp[i] = dp[j] + 1;
            }

            max = Math.max(max, dp[i]);
        }

        System.out.print(max);
    }
}

---