Python
import sys
sys.setrecursionlimit(10**6)
num = int(input())
arr = list(map(int, sys.stdin.readline().split()))
dp = [1] * num
dp[0] = arr[0]
for i in range(num):
for j in range(i):
if arr[j] < arr[i]:
dp[i] = max(dp[i], dp[j]+arr[i])
else:
dp[i] = max(dp[i], arr[i])
print(max(dp))
Python
복사
Java
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static Integer[] dp;
static int[] arr;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int num = Integer.parseInt(br.readLine());
dp = new Integer[num];
arr = new int[num];
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
for (int i = 0; i < num; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
// 0 ~ num-1 까지 탐색
for (int i = 0; i < num; i++) {
LIS(i);
}
// 최댓값 찾기
int max = dp[0];
for (int i = 1; i < num; i++) {
max = Math.max(max, dp[i]);
}
System.out.println(max);
}
static int LIS(int num) {
if (dp[num] == null) {
dp[num] = arr[num];
for (int i = num-1; i >= 0; i--) {
if (arr[i] < arr[num]) {
dp[num] = Math.max(dp[num], LIS(i)+arr[num]);
}
}
}
return dp[num];
}
}
Java
복사