boj)11722 - 가장 긴 감소하는 부분 수열
2020. 9. 20. 14:35ㆍPS/boj
import java.io.*;
import java.util.StringTokenizer;
public class boj_11722 {
static int[] dp;
static int[] val;
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
public static void main(String[] args) throws IOException {
int n = Integer.parseInt(br.readLine());
dp = new int[n+1];
val = new int[n+1];
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 1; i <= n; i++) {
val[i] = Integer.parseInt(st.nextToken());
}
for (int i = 1; i <= n; i++) {
int max = 0;
for (int j = 1; j <= n-1; j++) {
if (val[j] > val[i] && dp[j] > max) {
max = dp[j];
}
}
dp[i] = max + 1;
}
int ans = 1;
for (int i = 1; i <= n; i++) {
if (dp[i] > ans) ans = dp[i];
}
System.out.println(ans);
}
}
- dp[n] = dp[j] + 1;
- 1 <= j <= n-1, val[j] > val[i] 을 만족하는 최댓값
'PS > boj' 카테고리의 다른 글
boj)13398 - 연속합 2 (0) | 2020.09.21 |
---|---|
boj)11054 - 가장 긴 바이토닉 부분 수열 (0) | 2020.09.20 |
boj)11055 - 가장 큰 증가 부분 수열 (0) | 2020.09.19 |
boj)1932 - 정수 삼각형 (0) | 2020.09.19 |
boj)2156 - 포도주 시식 (0) | 2020.09.19 |