Dãy con tăng dài nhất (Longest Increasing Subsequence) trong Python

Giả sử chúng ta có một danh sách số nguyên chưa sắp xếp. Chúng ta phải tìm dãy con tăng dài nhất. Ví dụ, nếu đầu vào là [10,9,2,5,3,7,101,18], đầu ra sẽ là 4, vì dãy con tăng là [2,3,7,101].

Để giải quyết, chúng ta làm theo các bước sau:

• Tạo mảng duoi độ dài bằng độ dài nums, điền 0.

• Kích thước size := 0.

• Với mỗi x trong nums:

  • i := 0, j := size.
  • Khi i khác j:
    • mid := i + (j - i) // 2.
    • Nếu duoi[mid] < x, thì i := mid + 1, ngược lại j := mid.
  • duoi[i] := x.
  • size := max(i + 1, size).

• Trả về size.

Ví dụ

class Solution(object):
    def lengthOfLIS(self, nums):
        duoi = [0 for i in range(len(nums))]
        size = 0
        for x in nums:
            i = 0
            j = size
            while i != j:
                mid = i + (j - i) // 2
                if duoi[mid] < x:
                    i = mid + 1
                else:
                    j = mid
            duoi[i] = x
            size = max(i + 1, size)
        return size

ob1 = Solution()
print(ob1.lengthOfLIS([10,9,2,5,3,7,101,18]))

Đầu vào

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

Đầu ra

4