TIL
오늘 배운 것
boj 14002
import java.util.*;
import java.util.stream.Collectors;
import java.io.*;
public class Main {
public static void main(String[] args) throws Exception {
//System.setIn(new FileInputStream("input.txt"));
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
int N=Integer.parseInt(br.readLine());
List<Integer> arr=Arrays.stream(br.readLine().split(" "))
.map(i->Integer.parseInt(i))
.collect(Collectors.toList());
List<Integer> lis=new ArrayList<>();
List<Integer> results=new ArrayList<>();
for(int i=0;i<N;i++) {
lis.add(1);
}
int maxIdx=0;
int maxLIS=lis.get(maxIdx);
for(int i=0;i<lis.size();i++) {
//lis.set(i,1);
for(int j=0;j<i;j++) {
if(arr.get(j)<arr.get(i) && lis.get(j)+1>lis.get(i)) {
lis.set(i,lis.get(j)+1);
if(maxLIS<=lis.get(i)) {
maxLIS=lis.get(i);
maxIdx=i;
}
}
}
}
System.out.println(maxLIS);
results.add(arr.get(maxIdx ));
int rightBeforeLIS=maxLIS;
int rightBeforeIdx=maxIdx;
for(int j=maxIdx-1;j>=0;j--) {
if(lis.get(j)==rightBeforeLIS-1 && arr.get(j)<arr.get(rightBeforeIdx)){
rightBeforeLIS=lis.get(j);
rightBeforeIdx=j;
results.add(arr.get(j));
}
}
Collections.sort(results);
for(int i:results) {
System.out.print(i+" ");
}
}
}
/*
10 20 10 30 20 50
1 2 1 3 2 4
121325
121324
*/