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

1. 문제

www.acmicpc.net/problem/11055

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

2. 풀이

3. 코드

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

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		st = new StringTokenizer(br.readLine());

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

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

	}

}