BOJ 11055 가장 큰 증가하는 부분 수열

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

public class Main {
    static int N;
    static int[] A, dp;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());

        A = new int[N+1];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=1; i<=N; i++){
            A[i] = Integer.parseInt(st.nextToken());
        }

        // 0 1 100 2 50 60 3 5 6 7 8
        // 0 1 101 3 53 113

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

            res = Math.max(res, dp[i]);
        }

        System.out.println(res);
    }
}