leetcode: Longest Increasing Subsequence

2021/01/15 - [알고리즘 공부/boj] - boj 3745: 오름세

boj 3745: 오름세

 

위 문제와 동일하다. 지난번에 푼 기억이 있어서 비교적 수월하게 풀었다.

세그먼트 트리로도 한번 구현해 봐야하는데 언제하지...

class Solution {
	public int lengthOfLIS(int[] nums) {
		int n = nums.length;
		int[] lis = new int[n];

		lis[0] = nums[0];
		int lastIndex = 0;

		for (int i = 1; i < n; i++) {
			if (lis[lastIndex] < nums[i]) {
				lastIndex++;
				lis[lastIndex] = nums[i];
			} else {
				int index = findIndex(lis, nums[i], lastIndex);
				lis[index] = nums[i];
			}
		}
		return lastIndex + 1;
	}

	public static int findIndex(int[] lis, int target, int right) {
		int left = 0;

		while (left < right) {
			int mid = (left + right) / 2;
			if (lis[mid] == target) {
				return mid;
			}

			if (lis[mid] > target) {
				right = mid;
			} else {
				left = mid + 1;
			}
		}

		return right;
	}
}