11053 가장 긴 증가하는 부분 수열 java

<문제 해석>

부분 수열을 보면 마지막 값인 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]);
	}

}