[BOJ] 백준 [14002] 가장 긴 증가하는 부분수열4 JAVA

[BOJ] 백준 [14002] 가장 긴 증가하는 부분수열4 JAVA

import java.util. * ;

import java.io. * ;

import java.util.stream.Collectors;

public class Main{

public static void main( String [] args) throws IOException {

BufferedReader br = new BufferedReader( new InputStreamReader( System . in ));

StringBuilder answer = new StringBuilder();

int N = Integer. parseInt (br.readLine());

List < Integer > list = Arrays.stream(br.readLine(). split ( " " ))

.mapToInt(Integer:: parseInt ).boxed().collect(Collectors.toList());

ArrayList < Integer > result = new ArrayList < > ();

ArrayList < Node > path = new ArrayList < > ();

result. add (list.get( 0 )); path. add ( new Node( 0 ,list.get( 0 )));

int maxIndex = 0 ;

for ( int i = 1 ;i < N;i + + ){

int next = list.get(i);

int pos;

if (result.get(result.size() - 1 ) < next) {

result. add (next);

pos = result.size() - 1 ;

}

else {

pos = Collections.binarySearch(result, next);

if (pos < 0 ) pos = - pos - 1 ;

result.set(pos,next);

}

path. add ( new Node(pos,next));

maxIndex = Math.max(pos,maxIndex);

}

for ( int i = path.size() - 1 ;i > = 0 ;i - - ) {

if (path.get(i).index = = maxIndex) {

answer.insert( 0 , path.get(i).value + " " );

maxIndex - - ;

}

}

answer.insert( 0 ,result.size() + "

" );

System . out . print (answer);

}

static class Node{

int index;

int value;

public Node( int index, int value) {

this .index = index;

this .value = value;

}

}

}

from http://katastrophe.tistory.com/41 by ccl(A) rewrite - 2021-09-27 19:27:35