https://leetcode.com/problems/longest-increasing-subsequence

Let us keep in table dp[i] the minumum value so far, which is the end of increasing sequence of length i + 1. It can be not easy to digest, so let us go through example nums = [100, 9, 2, 9, 3, 7, 101, 6].

  1. dp = [100], because dp was empty, and there is nothig we can compare with.
  2. dp = [9] now, why? Because so far we found ony increasing subsequences with length 1 and we update dp[0].
  3. dp = [2] for the same reason.
  4. dp = [2, 9], because new element is greater than the last element in our table, it means we can create increasing sequence of length 2.
  5. dp = [2, 3], because new element is 3, and we are looking for the smallest index in our table, such that value is more than 3, so we update 9 to 3: we found increasing subsequence of size 2, which ends with 3 < 9.
  6. dp = [2, 3, 7], because new element is more than the last element.
  7. dp = [2, 3, 7, 101], the same reason.
  8. dp = [2, 3, 6, 101], because for new element 6 we looking for the smallest index in our table, such that value is more than 6, so we change element with value 7 to value 6.

Finally, answer is equal to 4, the length of dp. (note, that 2, 3, 6, 101 is not increasing subsequence, this values mean, that 2 is the minimum value for increasing subsequence of lentgh 1, 3 is the minumum value for increasing subsequence of length 2 and so on)

Complexity is O(n log n), because for each new element we need to do binary search in O(log n), and we do n steps.

Code. Here is staightforward code, which does exactly what I explained before.

class Solution:
    def lengthOfLIS(self, nums):
        dp = []
        for elem in nums:
            ind = bisect_left(dp, elem)
            if ind == len(dp):
                dp.append(elem)
            else:
                dp[ind] = elem
        return len(dp)

3 lines code: we can prefill our dp table with big numbers, in this way, we can directly update index and not being afraid to out-of-bounds indexes

class Solution:
    def lengthOfLIS(self, nums):
        dp = [10**10] * (len(nums) + 1)
        for elem in nums: dp[bisect_left(dp, elem)] = elem  
        return dp.index(10**10)

If you like the solution, you can upvote it on leetcode discussion section: Problem 0300