11053번: 가장 긴 증가하는 부분 수열 (acmicpc.net)
import java.util.Arrays;
import java.util.Scanner;
public class Main {
static int N;
static int[] arr;
static int[] d;
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner in=new Scanner(System.in);
N=in.nextInt();
arr=new int[N];
d=new int[N];
int answer=0;
Arrays.fill(d, 1);
for(int i=0;i<N;i++) {
arr[i]=in.nextInt();
}
d[0]=1;
for(int i=1;i<N;i++) {
for(int j=0;j<i;j++) {
if(arr[j]<arr[i]) {
d[i]=Math.max(d[i], 1+d[j]);
answer=Math.max(answer, d[i]);
}
}
}
if(answer==0) answer=1;
System.out.println(answer);
}
}
'코테 공부' 카테고리의 다른 글
[DP]문제#5. 등굣길 (0) | 2022.05.11 |
---|---|
[DP]문제#4. 이친수(백준 2193번),자바 (0) | 2022.04.14 |
[DP]문제#2. 연속합(백준 1912번),자바 (0) | 2022.04.14 |
[DP]문제#1. 1,2,3 만들기(백준 9095번),자바 (0) | 2022.04.14 |
[DFS/BFS]문제#1. 촌수 계산(백준 2644번), 자바 (0) | 2021.07.09 |