문제

가장 긴 증가하는 부분 수열 2

풀이

해당 문제는 LIS 문제이다. C++코드는 정말 짧게 끝나는데 자바 코드는 대부분 이분탐색을 해주어서 탐색 하는 값에 가장 가까운 큰 값을 구해주고 있다

do[0] = a[0]; // 처음 시작 부분은 기본으로 설정
int answer = 1; // 가장 긴 증가하는 부분 길이
for (int i = 1; i < n; i++) {
	// 가장 끝에 있는 값보다 크면 배열에 넣어준다
	if (dp[answer - 1] < a[i]) {
    	answer++;
        dp[answer - 1] = a[i];
    } else {
    	// a[i] 보다 큰 가장 가까운 값의 인덱스를 찾기
    	int index = lower_bound(answer, a[i]);
        a[index] = a[i];
    }
}

...

private int lower_bound(int index, int value) {
	int left = 0;
    int right = index;
    while (left < right) {
    	int mid = (left + right) / 2;
    	if (dp[mid] < value) {
			left = mid + 1;	
        } else {
        	right = mid;
        }
    }
    return left;
}

전체 코드

전체 코드

Reference

• https://st-lab.tistory.com/285