TIL
오늘 배운 것
최장증가 부분수열 재확인
- DP방식
for(int i=0;i<N;i++) {
LIS[i]=1;
for(int j=0;j<=i-1;j++) {
if(li.get(j)<li.get(i) && LIS[j]+1>LIS[i]) {
LIS[i]=LIS[j]+1;
}
}
}
O(N^2) 소요되는 일반적인 방법
- 이진탐색 활용
static int findPosByBinary(int n, List<Integer> li) {
int result=-1;
int left=0;
int right=li.size()-1;
int mid=(left+right)/2;
while(left<=right) {
mid=(left+right)/2;
if(li.get(mid)>n) {
right=mid-1;
} else if (li.get(mid)<n) {
left=mid+1;
} else {
result=mid;
break;
}
}
result=Math.max(left, right);
return result;
}
O(NlogN)이 소요되는 방법 이걸로 LIS배열속 변환 위치를 찾아서 바꾼다.
단, 중요한 것은 배열 속 값이 실제 LIS의 배열값이 아니라는 사실
단순히 부분수열의 갯수만 알 수 있다.