Longest Increasing Subsequence

Q: Độ phức tạp thời gian của dãy con tăng dài nhất là bao nhiêu?

Phương thức tails chạy trong thời gian O(n log n) và dùng O(n) bộ nhớ: mỗi phần tử cần một lần tìm kiếm nhị phân. Bảng xét mọi cặp chỉ số cần thời gian O(n²) , còn thử mọi dãy con cần O(2ⁿ) .

Trung bìnhQuy hoạch động Tìm kiếm nhị phân

+10

Bạn nhận được một danh sách số nguyên nums. Một dãy con giữ lại một số phần tử theo thứ tự ban đầu và bỏ các phần tử còn lại; các phần tử được giữ lại không cần nằm cạnh nhau. Hãy trả về độ dài của dãy con dài nhất có các giá trị tăng nghiêm ngặt từ trái sang phải. Hai giá trị bằng nhau liên tiếp không được tính là tăng.

Hàm

lengthOfLIS(nums: integer-array) → integer

numsinteger-array: Danh sách số nguyên để chọn
Trả vềinteger: độ dài của dãy con tăng nghiêm ngặt dài nhất

Ràng buộc

1 ≤ nums.length ≤ 2500
-10⁴ ≤ nums[i] ≤ 10⁴

Ví dụ

Đầu vào: nums = [3, 1, 8, 2, 5, 9, 4, 7]
Đầu ra: 4
Giải thích: 1, 2, 5, 9 tăng dần, và 1, 2, 5, 7 cũng vậy, cả 1, 2, 4, 7 nữa: độ dài là 4. Không có cách chọn năm giá trị nào mà vẫn tăng dần.

Câu hỏi mở rộng

Bạn có thể trả về một dãy con tăng dài nhất, cùng với độ dài của nó, mà vẫn chạy trong thời gian O(n log n) không?

Gợi ý

Mở từng gợi ý một. Mỗi gợi ý tiết lộ thêm một chút.

Đã mở 0/3

Lời giải

Một danh sách gồm n số có 2^n dãy con, quá nhiều để kiểm tra. Nếu với mỗi chỉ số, ta xác định độ dài của dãy con tăng dài nhất kết thúc chính xác tại đó thì sẽ có một bảng O(n²). Phiên bản nhanh nhất lưu giá trị nhỏ nhất mà một dãy con có độ dài nhất định có thể kết thúc tại đó, rồi dùng tìm kiếm nhị phân để xếp mỗi phần tử vào vị trí.

Lấy hoặc bỏ qua mọi phần tử

Đúng, nhưng không chạy xong với các test lớn nhất

Ý tưởng

Với mỗi phần tử, hãy quyết định có giữ lại hay không; bạn chỉ có thể giữ nums[i] nếu nó lớn hơn giá trị được giữ lại gần nhất. longest(i, prev) là số phần tử tối đa bạn vẫn có thể thêm từ chỉ số i trở đi, khi phần tử được giữ lại gần nhất nằm ở prev (hoặc -1). Bỏ qua phần tử thì ta có longest(i+1, prev); giữ lại thì ta có 1 + longest(i+1, i). Mỗi dãy con tăng dần là một đường đi tương ứng với một chuỗi lựa chọn này.

Với 1, 2, 3, ..., n, cả hai nhánh đều tiếp tục mở rộng và số lời gọi tăng gấp đôi với mỗi phần tử: 2^40 đã xấp xỉ 10^12. Tuy nhiên, chỉ có tối đa n² cặp khác nhau (i, prev).

Thuật toán

Viết longest(i, prev), trong đó prev là chỉ số của phần tử cuối cùng được giữ lại, hoặc -1.
Nếu i vượt quá phần tử cuối, trả về 0.
Bỏ qua nums[i]: best = longest(i+1, prev).
Nếu prev là -1 hoặc nums[i] > nums[prev], hãy giữ lại phần tử đó: best = max(best, 1 + longest(i+1, i)).
Trả về best. Đáp án là longest(0, -1).

def lengthOfLIS(nums):
    def longest(i, prev):
        # The longest increasing subsequence of nums[i:] whose values all exceed nums[prev].
        # prev is -1 while nothing has been taken.
        if i == len(nums):
            return 0
        best = longest(i + 1, prev)  # skip nums[i]
        if prev == -1 or nums[i] > nums[prev]:
            best = max(best, 1 + longest(i + 1, i))  # take nums[i]
        return best

    return longest(0, -1)

Dãy con dài nhất kết thúc tại mỗi chỉ số

Ý tưởng

Gọi ending[i] là độ dài của dãy con tăng dài nhất có phần tử cuối là nums[i]. Phần tử đứng trước nums[i], nếu có, là một nums[j] nào đó thỏa mãn j < i và nums[j] < nums[i], và phần dãy đến phần tử đó phải dài nhất có thể. Vậy ending[i] = 1 + max(ending[j]) với các j đó, hoặc bằng 1 nếu không có phần tử nào. Điền lần lượt từ trái sang phải.

Với [3, 1, 8, 2, 5, 9, 4, 7], bảng là [1, 1, 2, 2, 3, 4, 3, 4]: 5 có thể đứng sau 3, 1 hoặc 2, và dãy tốt nhất trong số đó có độ dài 2, nên ending[4] = 3. Đáp án là giá trị lớn nhất trong bảng, vì dãy con tốt nhất có thể kết thúc ở bất kỳ vị trí nào.

n(n-1)/2 phép so sánh: khoảng 3.1 × 10^6 với n = 2500.

Thuật toán

Tạo ending với mọi phần tử đều bằng 1.
Với mỗi i theo thứ tự từ trái sang phải, xét mọi j < i.
Nếu nums[j] < nums[i], đặt ending[i] bằng ending[j] + 1 nếu giá trị đó lớn hơn.
Trả về giá trị lớn nhất trong ending.

def lengthOfLIS(nums):
    n = len(nums)
    # ending[i]: the longest increasing subsequence that ends with nums[i]
    ending = [1] * n
    for i in range(1, n):
        for j in range(i):
            if nums[j] < nums[i] and ending[j] + 1 > ending[i]:
                ending[i] = ending[j] + 1
    return max(ending)

Đuôi nhỏ nhất bằng tìm kiếm nhị phân

Ý tưởng

Với mỗi độ dài, chỉ giữ lại giá trị nhỏ nhất mà một dãy con tăng có độ dài đó có thể kết thúc bằng: tails[k] ứng với độ dài k+1. Điểm kết thúc nhỏ hơn không bao giờ bất lợi: bất cứ giá trị nào có thể đứng sau số 9 cũng có thể đứng sau số 5. tails luôn tăng nghiêm ngặt: bỏ giá trị cuối của một dãy con tăng có độ dài k+2, bạn sẽ có một dãy độ dài k+1 kết thúc bằng giá trị nhỏ hơn.

Với mỗi x, hãy dùng tìm kiếm nhị phân để tìm phần tử cuối tiên ≥ x. Nếu không có, hãy thêm x: nó kéo dài dãy dài nhất. Nếu có, hãy thay phần tử cuối đó bằng x: dãy con ngắn hơn một phần tử kết thúc bằng giá trị nhỏ hơn x, nên x tạo ra dãy có cùng độ dài nhưng kết thúc bằng giá trị nhỏ hơn.

Ví dụ 1, tails lần lượt là [3], [1], [1, 8], [1, 2], [1, 2, 5], [1, 2, 5, 9], [1, 2, 4, 9], [1, 2, 4, 7]: độ dài 4. Trong [1, 2, 4, 9], số 4 xuất hiện sau số 9, nên chỉ độ dài của tails mới có ý nghĩa.

Thuật toán

Bắt đầu với một danh sách trống tails.
Với mỗi x trong nums, dùng tìm kiếm nhị phân để tìm chỉ số đầu tiên k sao cho tails[k] ≥ x.
Nếu không có phần tử đuôi nào ≥ x, hãy thêm x vào cuối danh sách.
Nếu không, đặt tails[k] = x.
Trả về độ dài của tails.

from bisect import bisect_left


def lengthOfLIS(nums):
    # tails[k]: the smallest last value of any increasing subsequence of length k + 1
    tails = []
    for x in nums:
        k = bisect_left(tails, x)  # the first tail that is >= x
        if k == len(tails):
            tails.append(x)  # x extends the longest subsequence so far
        else:
            tails[k] = x  # x is a smaller ending for length k + 1
    return len(tails)

Lỗi thường gặp và trường hợp biên

Trả về ending[n-1] thay vì phần tử lớn nhất. Với [1, 2, 3, 0], phần tử cuối là 1, nhưng đáp án là 3.
So sánh với ≤ thay vì <. [7, 7, 7, 7] phải trả về 1, không phải 4.
Trong phiên bản dùng tails, tìm tail đầu tiên thỏa mãn > x thay vì ≥ x. Khi đó, số 7 thứ hai được thêm vào sau số đầu tiên, tính các giá trị bằng nhau là tăng dần.
Nhầm lẫn với phiên bản liên tiếp. Trong ví dụ 1, dãy con liên tiếp tăng dài nhất gồm các phần tử liền kề là 2, 5, 9 (độ dài 3), trong khi đáp án là 4.
Giữ chỉ số bắt đầu từ 0 trong Lua hoặc R, nơi mảng bắt đầu từ 1. Dấu đánh dấu prev = -1 trở thành 0, và tìm kiếm nhị phân chạy trên các chỉ số từ 1 đến kích thước hiện tại.

Câu hỏi thường gặp3

Độ phức tạp thời gian của dãy con tăng dài nhất là bao nhiêu?

Phương thức tails chạy trong thời gian O(n log n) và dùng O(n) bộ nhớ: mỗi phần tử cần một lần tìm kiếm nhị phân. Bảng xét mọi cặp chỉ số cần thời gian O(n²), còn thử mọi dãy con cần O(2ⁿ).

Thuật toán sắp xếp patience trong bài toán dãy con tăng dài nhất là gì?

Đây là phương thức tails, được đặt tên theo một trò chơi bài. Mỗi đuôi là lá bài trên cùng của một chồng bài: một lá bài được đặt lên chồng bài ngoài cùng bên trái có lá trên cùng lớn hơn hoặc bằng giá trị của nó, hoặc bắt đầu một chồng mới. Số chồng bài chính là đáp án.

Thay vào đó, làm thế nào để tìm dãy con không giảm dài nhất?

Cho phép các phần tử liền kề bằng nhau. Trong bảng, hãy dùng nums[j] ≤ nums[i]. Với phương pháp tails, hãy tìm phần tử đuôi đầu tiên lớn hơn nghiêm ngặt x, để một giá trị bằng nhau sẽ nối dài danh sách thay vì thay thế một phần tử đuôi. Khi đó, [7, 7, 7, 7] trả về 4.

def lengthOfLIS(nums):
    # Viết code ở đây

Kiểm thử #1

Kiểm thử #2

Kiểm thử #3

Đối số

nums = [3, 1, 8, 2, 5, 9, 4, 7]

Đầu ra mong đợi

Longest Increasing Subsequence

Hàm

Ràng buộc

Ví dụ

Gợi ý

Lời giải

Lấy hoặc bỏ qua mọi phần tử

Dãy con dài nhất kết thúc tại mỗi chỉ số

Đuôi nhỏ nhất bằng tìm kiếm nhị phân

Lỗi thường gặp và trường hợp biên

Câu hỏi thường gặp3

Bài tập tương tự