Python
import sys
sys.setrecursionlimit(10**6)
num = int(input())
arr = list(map(int, sys.stdin.readline().split()))
arr_reverse = arr[::-1]
dp_f = [1] * num
dp_r = [1] * num
dp_result = [0] * num
for i in range(num):
for j in range(i):
if arr[j] < arr[i]:
dp_f[i] = max(dp_f[i], dp_f[j]+1)
if arr_reverse[j] < arr_reverse[i]:
dp_r[i] = max(dp_r[i], dp_r[j]+1)
for i in range(num):
dp_result[i] = dp_f[i] + dp_r[num-1-i]-1
print(max(dp_result))
Python
복사
Java
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static Integer[] dpFront;
static Integer[] dpRear;
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());
dpFront = new Integer[num];
dpRear = 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);
LDS(i);
}
int max = -1;
for (int i = 0; i < num; i++) {
max = Math.max(max, dpFront[i] + dpRear[i]);
}
System.out.println(max-1);
}
static int LIS(int num) {
if (dpFront[num] == null) {
dpFront[num] = 1;
for (int i = num-1; i >= 0; i--) {
if (arr[i] < arr[num]) {
dpFront[num] = Math.max(dpFront[num], LIS(i)+1);
}
}
}
return dpFront[num];
}
static int LDS(int num) {
if (dpRear[num] == null) {
dpRear[num] = 1;
for (int i = num+1; i < dpRear.length; i++) {
if (arr[i] < arr[num]) {
dpRear[num] = Math.max(dpRear[num], LDS(i)+1);
}
}
}
return dpRear[num];
}
}
Python
복사