<문제 해석>
부분 수열을 보면 마지막 값인 50부터 생각을 해보자.
지목한 값이 50일 경우 앞에 올 수 있는 가장 가까운 값은 30이다. 30일 경우 가장 가까운 값은 20이고, 20일 경우에 앞에 올 수 있는 값을 10이다.
즉, 50을 마지막 DP값이라고 생각했을 때, 30의 DP값을 이미 계산 되어 있다고 생각하면 쉽게 이해가 된다.
이중 for문을 구성하여 지목한 값과 그 전의 값들을 비교하여 값이 작으면 DP값을 비교하면서 전의 DP값이 큰것을 마지막 DP값으로 계속 넣어주면 되겠다.
수열의 최소 길이가 1이므로 DP배열의 값들을 1로 초기화한 후 아래와 같이 점화식을 구성하였다.
for(int i=0;i<6;i++){
for(int j=0;j<i;j++){
if(A[i]>A[j]){
dp[i] = Math.max(dp[j]+1, dp[i])
}
}
}
이 점화식을 토대로 소스 코드를 구성해 보았다.
<소스코드>
import java.util.Arrays;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] arr = new int[n];
int[] dp = new int[n];
for (int i = 0; i < n; ++i) {
arr[i] = sc.nextInt();
//dp 값 1로 지정
dp[i] = 1;
}
for(int i = 1; i < n; ++i){
for (int j = 0; j < i; ++j){
if (arr[i] > arr[j]){
//앞의 숫자와 비교하여 작을 경우 전에 계산한 길이의 최대값을 dp에 넣어준다.
//ex) 10, 14, 11, 12 의 케이스를 계산
dp[i] = Math.max(dp[j] + 1, dp[i]);
}
}
}
Arrays.sort(dp);
System.out.println(dp[n-1]);
}
}
