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

dp 문제입니다.

 

증가하는 부분 수열이 여러 개 나올 수 있습니다.

특히, 어떤 인덱스에 이전에 존재하던 증가하는 부분 수열보다 작은 수가 등장한 이후로

이전에 존재하던 증가하는 부분 수열보다는 작지만 계속해서 증가를 하는 수열이 나온다면?

가장 긴 증가하는 부분 수열은 갑자기 등장한 수부터 시작하는 증가하는 부분 수열이 될 것입니다.

 

그렇기에 이각 항마다 가장 긴 증가하는 부분 수열의 길이를 저장해 답을 구합시다.

 

보다 이해를 돕기 위해 수열 {5, 10, 3, 30, 5, 7, 20} 을 예로 들어보겠습니다.

d[i]는 i항에서 가장 긴 증가하는 부분 수열의 길이입니다.

 

d[1] = 1 | {5} 입니다.

d[2] = 2 | {5, 10} 입니다.

d[3] = 1 | {3} 입니다.

d[4] = 3 | {5, 10, 30} 입니다. {5, 30}과 {2, 30}도 증가하는 부분 수열이나 길이가 짧아 탈락했습니다.

d[5] = 2 | {3, 5} 입니다.

d[6] = 3 | {3, 5, 7} 입니다. {5, 7}과 {3, 7}도 증가하는 부분 수열이나 길이가 짧아 탈락했습니다.

d[7] = 4 | {3, 5, 7, 20} 입니다. d[1] + 1, d[2] + 1, d[3] + 1, d[5] + 1은 길이가 짧아 탈락했습니다.

 

이중 포문을 돌며 j번째 항마다 i번째 항보다 작은 항이 있다면,

j번째 항을 마지막으로 하는 수열에 현재 수열을 추가한 길이를 구하여

j<i일 동안 계속 i번째 항을 마지막으로 하는 수열의 최대 길이를 갱신합니다.

 

import java.io.*;
import java.util.*;

public class Main {

	public static void main(String[] args) throws IOException {
		
		Scanner sc = new Scanner(System.in);
		
		int d[] = new int[1001];
		int a[] = new int[1001];
		int answer = 1;
		int n = sc.nextInt();
		
		for(int i=1; i<n+1; i++)
			a[i] = sc.nextInt();
		
		// d[i] : i번째 항을 마지막으로 하는 수열 중 최대 길이
		d[1] = 1; // d[1]은 항상 1이다.
		for(int i=2; i<n+1; i++) {
			d[i] = 1;
			for(int j=1; j<i; j++) {
				if(a[j] < a[i])
					d[i] = Math.max(d[i], d[j]+1);

			}
			answer = Math.max(answer, d[i]);
		}
		System.out.println(answer);
	}

}