[코드트리/INTERMEDIATE LOW] 최대 감소 부분 수열 (JAVA)

📖 문제

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

 

 

💡  풀이 방식

• DP (LDS)

dp[ i ] : 마지막으로 고른 원소 위치가 i인 부분 수열 中 최장 감소 부분 수열의 길이

 

현재 위치의 값 arr[i]와 현재 위치보다 앞쪽 j에 있는 값들과 값을 비교해

현재 위치에 있는 값 arr[j]가 앞쪽에 있는 값 arr[i]보다 작다면 감소하는 부분 수열이므로

dp 배열을 갱신한다.

for(int i = 0 ; i < N ; i++) {
	for(int j = 0 ; j < i ; j++) {
    	if(arr[j] > arr[i]) {
        	dp[i] = Math.max(dp[i], dp[j] + 1);
        }
    }
}

 

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
 
        int N = Integer.parseInt(br.readLine());
        int[] arr = new int[N];
        int[] dp = new int[N];
 
        st = new StringTokenizer(br.readLine(), " ");
        for(int i = 0 ; i < N ; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
            dp[i] = 1;    // 초기 dp 배열 값을 1로 초기화하기
        }
 
        for(int i = 0 ; i < N ; i++) {
            for(int j = 0 ; j < i ; j++) {    // i보다 앞쪽에 있는 원소들 중 arr[i]보다 큰 값이 있다면, dp 배열 갱신
                if(arr[j] > arr[i]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }                    
            }
        }
 
        int max = 1;
        for(int i : dp) {
            max = Math.max(max, i);
        }
        System.out.println(max);
    }
}

 

 

 

---

 

 

1회독	2회독	3회독	4회독	5회독
V