Longest Increasing Subsequence

Problem

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

Solution

• DP. Second solution can be O(nlg(n))
• First solution: Two for loops checking for each number, what would be the max subsequence based on 1 to n-1.
• Second solution: Build a sequence, whose i-th position stores the best option (number) for subsequences of length i.
• Use binary search to make the search log(n)
• The second approach does not build a single subsequence does produce the correct length.

# First: DP, O(N2)

from typing import List

def lengthOfLIS(self, nums: List[int]) -> int:

    local_sol = [1]*(len(nums))

    global_sol = 1

    for i in range(1, len(nums)):

        for j in range(i):

            if nums[i] > nums[j]:

                local_sol[i] = max(local_sol[i], local_sol[j]+1)

            global_sol = max(global_sol, local_sol[i])

    return global_sol

# Second: DP, O(N2)

def lengthOfLIS(self, nums: List[int]) -> int:

    seq = [nums[0]]

    for num in nums[1:]:

        if num > seq[-1]:

            seq.append(num)

        else:

            i = 0

            while seq[i] < num:

                i += 1

            seq[i] = num

   

    return len(seq)

# Third DP, O(N lg(N))

import bisect

def lengthOfLIS(self, nums: List[int]) -> int:

    seq = []

    for num in nums:

        i = bisect_left(seq, num)

        if i == len(seq):

            seq.append(num)

        else:

            seq[i] = num

   

    return len(seq)