Array String Dynamic Programming Memoization Tabulation
Proficient Level

Implement the longestIncreasingSubsequenceOptimizedLength method that returns the LIS length using optimized binary-search based logic.

The input contains an integer array nums and its length size. Your task is to return the length of the longest increasing subsequence.

A subsequence keeps the original order of elements but does not need to use consecutive elements. The values in the selected subsequence must be strictly increasing.

For example, in [10,9,2,5,3,7,101,18], one longest increasing subsequence is [2,3,7,101], so the answer is 4.

Example 1
Input:
nums (int[]) = [10,9,2,5,3,7,101,18]
size (int) = 8
Return:
(int) 4
Example 2
Input:
nums (int[]) = [0,1,0,3,2,3]
size (int) = 6
Return:
(int) 4
Example 3
Input:
nums (int[]) = [7,7,7,7]
size (int) = 4
Return:
(int) 1

Use the optimized tails array technique with binary search.

tails[length] stores the smallest possible ending value of an increasing subsequence of that length plus one. For each number, find the first position in tails where the value is greater than or equal to the current number, then replace it.

This does not store the actual subsequence, but the size of tails gives the length of the longest increasing subsequence.

Pseudocode:

function longestIncreasingSubsequenceOptimizedLength(nums, size):
    tails = empty array
    for each num in nums:
        index = lowerBound(tails, num)
        if index == length(tails):
            append num to tails
        else:
            tails[index] = num
    return length(tails)
function lowerBound(arr, target):
    left = 0
    right = length(arr)
    while left < right:
        mid = left + (right - left) / 2
        if arr[mid] < target:
            left = mid + 1
        else:
            right = mid
    return left
Run your code to see the result.