Fast Longest Increasing Subsequence

Problem

Return the length of the longest strictly increasing subsequence of arr using the O(n log n) patience sorting method.

Maintain tails where tails[l] is the smallest possible tail of an increasing subsequence of length l + 1, binary searching the first tail that is not smaller than the current value. Return 0 for an empty list.

Hint

Replacing the first tail not smaller than x keeps every tail as small as possible.

Test cases

case 1

in: [[10,9,2,5,3,7,101,18]]

expected: 4

case 2

in: [[1,2,3,4,5]]

expected: 5

case 3

in: [[5,4,3,2,1]]

expected: 1

case 4

in: [[]]

expected: 0

case 5

in: [[7,7,7]]

expected: 1

Starter codePython

def lis_length_fast(arr):
    # Your code here
    pass

5 test cases · run your code against them in the editor