백준 11053번 가장 긴 증가하는 부분 수열 Java

BOJ 11053번 가장 긴 증가하는 부분 수열 Java

 

가장 긴 증가하는 부분 수열의 개념을 먼저 알아야한다. (자세한설명 나무위키)

수열의 정렬을 건드리지 않고, 가장 적은 숫자를 제거해서 오름차순인 수열을 만들어내는 것이다.

 

백준은 테스트케이스가 다양한 상황을 고려하지 못해서 개인적으로 만들어봤다.

테스트케이스:  {1 2 1 3 2 6 4 5}

🎈 1 2 1 3 2 6 4 5

🎈 1 2 1 3 2 6 4 5

이 두가지 경우 중 가장 긴 것을 선택해야한다.

 

🎈 1 2 3 6

🎈 1 2 3 4 5

이 둘은 각각 { 1 2 3 } + 6 과 { 1 2 3 } + 4 5 한 것중 긴 것을 택한 것.

 

For 1 ~ N

  For 1~N-1

의 이중포문으로 시간복잡도는 O(NlogN) 이라고 한다.