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

https://www.acmicpc.net/problem/11053

11053번: 가장 긴 증가하는 부분 수열

점화식은 for를 돌면서 본인보다 이전에 나온 수의 크기가 더 작으면 그수에 1 증가 한 수를 dp에 저장하는 방법으로 해결했다. 이런 식으로 해결하면 현재값이 나온 수들 중 가장 큰 값이라면 이전까지 나온 수들 중 가장 큰 dp값에 1을 더하게 된다.

if(arr[j]<arr[i] && dp[i]<=dp[j] ){

   dp[i] = dp[j] +1;

 

}

 

 

풀이

 

package 동적계획법;
 
import java.io.*;
import java.util.*;
 
public class 가장긴_증가하는_부분수열 {
    public static void main(String[] args) throws Exception {
 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] arr = new int[n + 1];
        int[] dp = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.fill(dp, 1);
        for (int i = 2; i <= n; i++) {
 
            for (int j = 1; j < i; j++) { //이전에 지나온 수열들 중 가장 큰 값
                if (arr[j] < arr[i] && dp[j] >= dp[i]) {
                    dp[i] = dp[j] + 1;
                }
            }
        }
        int res =  0;
        for(int i:dp){
            res = Math.max(i,res);
        }
        System.out.println(res);
    }
 
 
}