[백준] 11055번 가장 큰 증가 부분 수열

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

11055번: 가장 큰 증가 부분 수열

점화식 : dp[i] = dp[i-1] + arr[i]

import java.util.*;
import java.io.*;

public class Main {

    public static void main(String[] args) throws Exception {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n + 1];
        int[] dp = new int[n + 1];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i = 1; i <= n; i++ ) {
        	arr[i] = Integer.parseInt(st.nextToken());
        }

        dp[1] = arr[1];
        int max =  dp[1];
        for(int i = 2; i <= n; i++) {
            dp[i] = arr[i];
            for(int j = 1; j < i ; j++) {
            	if(arr[i] > arr[j]) {
            		dp[i] = Math.max(dp[i], dp[j] + arr[i]);
            	}
        	}
        max = Math.max(max, dp[i]);
        }
        System.out.println(max);
    }

}