Python
import sys
sys.setrecursionlimit(10**6)
num = int(input())
arr = list(map(int, sys.stdin.readline().split()))
dp = [1] * num
for i in range(num):
for j in range(i):
if arr[j] > arr[i]:
dp[i] = max(dp[i], dp[j]+1)
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());
}
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] = 1;
for (int i = num-1; i >= 0; i--) {
if (arr[i] > arr[num]) {
dp[num] = Math.max(dp[num], LIS(i)+1);
}
}
}
return dp[num];
}
}
Java
복사