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

다이나믹 프로그래밍 문제입니다.
수열이 주어질 때 가장 긴 감소하는 부분 수열을 찾아야합니다.

https://j3sung.tistory.com/941

[Java] 백준 11053번 가장 긴 증가하는 부분 수열

가장 긴 증가하는 부분 수열 문제와 거의 동일합니다.

2중 for문을 사용해서 차례대로 탐색합니다.
현재 위치 보다 오른쪽에 있으면서 값이 더 작은 경우
현재 위치DP값(현재까지 계산된 가장 큰 길이) + 1, 비교하는 위치 DP값 중 큰 값으로 변경해줍니다.

DP[j] = Math.max(DP[j], DP[i] + 1);

위의 과정을 전부 반복해주어 최종적으로 가장 긴 길이의 증가하는 수열을 찾습니다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = null;
		
		int ans = 0;
		int n = Integer.parseInt(br.readLine());
		int[] arr = new int[n+1];
		int[] DP = new int[n+1];
		
		st = new StringTokenizer(br.readLine());
		for(int i=1; i<=n; ++i) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		
		arr[0] = Integer.MAX_VALUE;
		for(int i=0; i<=n; ++i) {
			for(int j=i+1; j<=n; ++j) {
				if(arr[i] > arr[j]) {  
					DP[j] = Math.max(DP[j], DP[i] + 1);
				}
			}
		}
		
		for(int i=1; i<=n; ++i) {
			ans = Math.max(ans, DP[i]);
		}		
		
		bw.write(ans + "\n");		
		bw.close();
	}
}