[백준]11055 가장 큰 증가 부분 수열 (java)

풀이

이 문제는 전형적인 LIS문제중 하나이다. 문제는 크게 어려울것이 없이 기준값이 정해지면 인덱스의 처음부터 마지막까지 돌아가면서 만약 증가하는 부분수열을 만족한다면 DP에 저장하면 된다. 그렇게 기준값을 끝까지 돌리고 난후 DP에 저장되어있는 수들중 가장큰수를 출력하면 된다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

class Main{

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), "");
        int N = Integer.parseInt(st.nextToken());
        int []arr = new int[N];
        int []dp = new int[N];
        st = new StringTokenizer(br.readLine(), " ");

        for(int i=0; i<N; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }

        dp[0] = arr[0];
        for(int i=1; i<N; i++){
            dp[i] = arr[i];
            for(int j=0; j<i; j++){
                if(arr[i] > arr[j]){
                    dp[i] = Math.max(dp[i], dp[j]+arr[i]);
                }
            }
        }

        int max = 0 ;
        for(int i=0; i<N; i++){
            if(max < dp[i])
                max = dp[i];
        }

        System.out.println(max);
    }

}