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



*/

results matching ""

    No results matching ""