longestIncreasingSubsequence.ts

/*
Given an integer array nums, return the length of the longest strictly increasing subsequence.

 

Example 1:
Input: nums = [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.

Example 2:
Input: nums = [0,1,0,3,2,3]
Output: 4

Example 3:
Input: nums = [7,7,7,7,7,7,7]
Output: 1
*/

function lengthOfLIS(nums: number[]): number {
	// Approach 1: Brute force
	// backtracking all the subsequence

	const maxLengths = new Array(nums.length).fill(1);

	for (let index = 1; index < nums.length; index++) {
		for (let subIndex = 0; subIndex < index; subIndex++) {
			if (nums[subIndex] < nums[index]) {
				maxLengths[index] = Math.max(maxLengths[index], maxLengths[subIndex] + 1);
			}
		}
	}

	return Math.max(...maxLengths);
}

function lengthOfLISWithBinarySearch(nums: number[]): number {
	// Approach 2: Patience sorting with binary search — O(n log n)
	// tails[i] = smallest tail of all increasing subsequences of length i+1
	const tails: number[] = [];

	for (const num of nums) {
		let left = 0, right = tails.length;

		while (left < right) {
			const middle = (left + right) >> 1;
			if (tails[middle] < num) left = middle + 1;
			else right = middle;
		}

		tails[left] = num; // replace or append
	}

	console.log(tails);
	
	return tails.length;
}

console.log(lengthOfLISWithBinarySearch([0, 1, 0, 3, 2, 3]));