링크

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

문제

풀이

이 문제는 풀다가 값을 어떻게 저장해야될지 감이 안잡혀서 풀이를 봤다.
dp에다가 현재값과 이전값들을 비교하면서 dp를 갱신해주면 된다.
예를들어 10 20 10 30 20 50 이라는 배열이 있으면
i = 1
현재값 : 20
이전값 : 10, 현재값이 더 크므로 dp[2] = dp[1] + 1

i = 2
현재값 : 10
이전값 : 10, 20 둘다 현재값이 보다 크거나 같으므로 x

i = 3
현재값 : 30
이전값 : 10, 20, 10
i = 3일때 현재값 30
j = 0, 이전값 10, dp[i] = dp[j] + 1(여기에서는 dp[i] = 2가 된다.)
j = 1, 이전값 20, dp[i] = dp[j] + 1(여기에서는 dp[i] = 3이 된다.)
j = 2, 이전값 10, 여기에서 dp[i] = dp[j] + 1해버리면 dp[2]인 부분이 1이다 그래서 2가 되버린다. 그러므로 Math.max(dp[i], dp[j] + 1)을 통해 최대값을 저장하면 된다.

코드

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

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));

        int testCase = Integer.parseInt(br.readLine());

        String[] arr = br.readLine().split(" ");

        int[] numbers = new int[testCase];
        for(int i=0;i<arr.length;i++){
            numbers[i] = Integer.parseInt(arr[i]);
        }

        int[] dp = new int[numbers.length];
        Arrays.fill(dp, 1);

        for(int i=1;i<dp.length;i++){

            for(int j=0;j<i;j++){

                if(numbers[i] > numbers[j]){
                    dp[i] = Math.max(dp[i], dp[j]+1);
                }

            }
        }
        
        int max = 0;
        for(int element : dp){
            max = Math.max(element, max);
        }

        System.out.println(max);
    }


}