백준 11055번 가장 큰 증가하는 부분순열

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

public class LongestIncreasingSubsequence {
    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[] A = new int[N+1];
        int[] dp = new int[N+1];
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <=N; i++) {
            A[i] = Integer.parseInt(st.nextToken());
        }
        dp[1] = A[1];
        int answer = dp[1];
        for (int i = 2; i <N+1; i++) {
            int max = 0;
            for (int j = 1; j < i; j++) {
                if(A[j]<A[i]){
                    max = Math.max(max,dp[j]);
                }
            }
            dp[i] = max+A[i];
            answer = Math.max(answer,dp[i]);
        }
        System.out.println(answer);
    }
}

풀이방법

dp배열에 넣어야 할 값: 현재 값보다 작은 값 중에 증가하는 순열의 합이 가장 큰값

1 100 5 3 50 일때, dp[5]가 가능한 증가하는 순열은 1 5 50, 1 3 50 두가지가 있다. 둘 중 큰값을 선택한다.

이때 1 5, 1 3 은 각각 dp[3], dp[4]이다.
즉 dp[5]는 dp[3]+ A[5], dp[4] + A[5] 중 더 큰 값이 들어가게 된다.

📢점화식으로 나타내면 dp[i] = 이전 dp값중 최댓값 + A[i] 이다.
이때, 주의할 점은 증가하는 순열이므로, dp값중 최댓값을 찾을때, 현재 값보다 작은 값일때만 탐색해야 한다는 점이다.