Hai Cách Tìm Longest Increasing Subsequence — và Tại Sao O(n log n) Hoạt Động

LeetCode 300 yêu cầu tìm độ dài của dãy con tăng dần nghiêm ngặt dài nhất trong một mảng số nguyên. Dãy con, không phải subarray — các phần tử không cần liền kề, nhưng phải giữ nguyên thứ tự tương đối trong mảng gốc, và mỗi phần tử phải lớn hơn phần tử trước đó theo nghĩa nghiêm ngặt.

Ví dụ chuẩn là [10, 9, 2, 5, 3, 7, 101, 18], với đáp án là 4 vì [2, 3, 7, 101] là dãy con tăng dần nghiêm ngặt dài nhất có thể chọn ra (cũng có các dãy khác cùng độ dài: [2, 5, 7, 101], [2, 3, 7, 18]).

Bài này nằm ở giao điểm của DP và binary search theo cách mà phần lớn bài toán subsequence không có. DP O(n²) cho bạn trực giác đúng về state. Binary search O(n log n) cho bạn thứ thú vị hơn: một greedy invariant không hiển nhiên cho đến khi nhìn đủ lâu.

Constraints nói gì

n lên đến 2500. Điều đó đặt O(n²) ở khoảng 6.25 triệu phép tính — nhanh, thoải mái trong mọi time limit hợp lý. O(n³) đã là ranh giới mờ. Brute force thuần túy (thử từng subsequence) là 2^2500 — không có nghĩa gì.

Vậy n = 2500 không phải constraint loại bỏ brute force exponential; đó là constraint khiến O(n²) chấp nhận được và O(n log n) là follow-up tối ưu chứ không phải yêu cầu bắt buộc. Điều này thay đổi cách bạn suy nghĩ: DP O(n²) là câu trả lời phỏng vấn hoàn toàn hợp lệ, không phải bước đệm bị loại bỏ.

Các giá trị nằm trong khoảng -10^4 đến 10^4. Không có gì thay đổi về mặt thuật toán — không có modular arithmetic, không overflow, không bucket trick. Chỉ đơn giản là bạn không cần lo về giá trị phần tử làm key dictionary.

DP O(n²): cách formulate tự nhiên

Định nghĩa state làm cho recurrence tự hiển nhiên. Đặt dp[i] là độ dài của LIS kết thúc chính xác tại index i. Mỗi phần tử tự tạo thành dãy con độ dài 1, nên dp[i] = 1 là baseline cho mọi i.

Để tính dp[i], duyệt qua mỗi index j < i. Nếu nums[j] < nums[i], bạn có thể mở rộng bất kỳ LIS nào kết thúc tại j bằng cách thêm nums[i] vào. Vậy dp[i] = max(dp[i], dp[j] + 1) bất cứ khi nào nums[j] < nums[i].

Đáp án là max(dp) — giá trị lớn nhất trong toàn bộ mảng dp.

class Solution:
    def lengthOfLIS(self, nums: list[int]) -> int:
        n = len(nums)
        dp = [1] * n
 
        for i in range(1, n):
            for j in range(i):
                if nums[j] < nums[i]:
                    dp[i] = max(dp[i], dp[j] + 1)
 
        return max(dp)

public class Solution {
    public int LengthOfLIS(int[] nums) {
        int n = nums.Length;
        int[] dp = new int[n];
        Array.Fill(dp, 1);
 
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    dp[i] = Math.Max(dp[i], dp[j] + 1);
                }
            }
        }
 
        return dp.Max();
    }
}

Trace từng bước với [10, 9, 2, 5, 3, 7, 101, 18]:

Ban đầu: dp = [1, 1, 1, 1, 1, 1, 1, 1]
         idx:  0  1  2  3  4  5  6  7

i=1 (val=9):  j=0, nums[0]=10 >= 9, bỏ qua.  dp[1]=1
i=2 (val=2):  j=0, 10>=2 bỏ; j=1, 9>=2 bỏ.  dp[2]=1
i=3 (val=5):  j=0,1 bỏ; j=2, 2<5 -> dp[3]=max(1,dp[2]+1)=2.  dp[3]=2
i=4 (val=3):  j=0,1 bỏ; j=2, 2<3 -> dp[4]=max(1,2)=2; j=3, 5>=3 bỏ.  dp[4]=2
i=5 (val=7):  j=2, 2<7 -> dp[5]=max(1,2)=2; j=3, 5<7 -> dp[5]=max(2,3)=3; j=4, 3<7 -> dp[5]=max(3,3)=3.  dp[5]=3
i=6 (val=101): tất cả < 101. dp[6]=max(dp[j]+1) = dp[5]+1=4.  dp[6]=4
i=7 (val=18):  j=2,3,4,5 < 18; dp[7]=max(2,3,3,4)=4.  dp[7]=4

dp = [1, 1, 1, 2, 2, 3, 4, 4]
max(dp) = 4

Trace cho thấy điều đáng chú ý: index 6 và 7 đều cho độ dài 4. Vì cả [2,3,7,101] lẫn [2,3,7,18] đều dài 4. Mảng dp lưu độ dài LIS tốt nhất kết thúc tại mỗi vị trí — không phải một subsequence cụ thể duy nhất.

Time: O(n²). Space: O(n) cho mảng dp.

O(n log n): insight từ patience sorting

Follow-up hỏi liệu bạn có thể làm O(n log n) không. Cách tiếp cận đạt được điều đó dùng một greedy invariant gọi là patience sorting, và đáng để hiểu tại sao nó hoạt động thay vì chỉ học thuộc code.

Duy trì một mảng tails trong đó tails[k] giữ giá trị đuôi nhỏ nhất có thể của bất kỳ dãy con tăng nào có độ dài k + 1 được thấy cho đến nay. Cụm từ cuối cùng đó là chìa khóa: không phải đuôi của một subsequence cụ thể — mà là giá trị đuôi nhỏ nhất trong tất cả subsequence có độ dài tối ưu đó. Đuôi nhỏ hơn tốt hơn vì để lại nhiều chỗ cho các phần tử tương lai mở rộng dãy.

Với mỗi phần tử mới num:

• Nếu num lớn hơn tất cả trong tails, nó mở rộng LIS dài nhất đã thấy. Append vào cuối.
• Ngược lại, tìm vị trí trái nhất trong tails mà tails[pos] >= num. Thay tails[pos] bằng num. Điều này không phá hủy subsequence — nó chỉ ghi nhận rằng bây giờ tồn tại một subsequence độ dài (pos+1) với đuôi nhỏ hơn, tốt hơn hoàn toàn.

tails luôn được sắp xếp (đó là lý do binary search hoạt động trên nó), và độ dài của nó ở cuối bằng độ dài LIS. Lưu ý: bản thân tails không nhất thiết là một subsequence hợp lệ từ nums — nó là cấu trúc bookkeeping, không phải tái tạo LIS thực tế.

Mỗi lần gọi bisect_left tìm điểm chèn trong O(log n), và ta xử lý n phần tử — tổng O(n log n).

import bisect
 
class Solution:
    def lengthOfLIS(self, nums: list[int]) -> int:
        tails: list[int] = []
 
        for num in nums:
            pos = bisect.bisect_left(tails, num)
            if pos == len(tails):
                tails.append(num)
            else:
                tails[pos] = num
 
        return len(tails)

public class Solution {
    public int LengthOfLIS(int[] nums) {
        var tails = new List<int>();
 
        foreach (int num in nums) {
            int pos = BinarySearchLeft(tails, num);
            if (pos == tails.Count) {
                tails.Add(num);
            } else {
                tails[pos] = num;
            }
        }
 
        return tails.Count;
    }
 
    private static int BinarySearchLeft(List<int> arr, int target) {
        int left = 0, right = arr.Count;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] < target) left = mid + 1;
            else right = mid;
        }
        return left;
    }
}

Phiên bản C# implement thủ công bisect_left vì List<T> không có built-in tương đương. Array.BinarySearch trả về bitwise complement khi không tìm thấy, dùng được nhưng xấu; implementation thủ công rõ ràng hơn nhiều.

Time: O(n log n). Space: O(n) cho tails.

Tại sao greedy invariant giữ vững

Invariant rằng tails luôn được sắp xếp không hiển nhiên ngay từ đầu. Hãy để tôi chỉ ra tại sao việc thay thế bảo tồn điều đó.

Trước khi xử lý num, tails được sắp xếp: tails[0] < tails[1] < ... < tails[k]. Ta tìm pos sao cho tails[pos] >= num và tails[pos-1] < num (hoặc pos = 0). Ta thay tails[pos] bằng num. Sau khi thay:

• tails[pos-1] < num (nếu pos > 0): đúng theo định nghĩa của pos.
• num <= tails[pos] (giá trị gốc): ta thay bằng thứ nhỏ hơn hoặc bằng.
• tails[pos] <= tails[pos+1] (vị trí tiếp theo): num <= tails[pos] < tails[pos+1], nên điều này giữ.

Vậy sorted invariant được bảo tồn. Và vì tails luôn được sắp xếp, binary search luôn hợp lệ. Invariant tự bootstrap chính nó.

Các edge case thực sự quan trọng

Một phần tử: nums = [5]. Vòng lặp ngoài xử lý một phần tử, append vào tails, trả về len(tails) = 1. Cả hai cách đều xử lý được — vòng lặp trong của DP trống với i=0, baseline là 1.

Tất cả phần tử bằng nhau: nums = [7, 7, 7, 7, 7, 7, 7]. Tăng nghiêm ngặt nghĩa là phần tử bằng nhau không thể mở rộng dãy. Trong DP, nums[j] < nums[i] luôn sai, nên mọi dp[i] giữ nguyên 1. Trong binary search, bisect_left tìm vị trí 0 cho mọi 7 (vì tails[0] = 7 >= 7), nên ta cứ thay vị trí 0. tails luôn dài 1. Đáp án: 1.

Giảm dần nghiêm ngặt: nums = [5, 4, 3, 2, 1]. Trong DP, mỗi phần tử mới nhỏ hơn tất cả phần tử trước, không có extension. Trong binary search, mỗi phần tử thay vị trí 0. tails cuối cùng = [1], dài 1.

Đã tăng dần: nums = [1, 2, 3, 4, 5]. Mỗi phần tử append vào tails. Độ dài cuối là 5. Trong DP, mỗi dp[i] = i + 1. Đúng.

Hai phần tử mà phần tử đầu lớn hơn: nums = [3, 1]. DP: dp[0]=1, dp[1]=1 (vì 3 >= 1). Binary search: tails=[3], rồi 1 thay vị trí 0 -> tails=[1], dài 1. Đáp án: 1.

So sánh hai cách tiếp cận

Space là O(n) cho cả hai. Không cái nào giảm được: DP cần lưu toàn bộ giá trị dp[i], binary search cần tails dài tối đa n.

Pattern DP nhìn lại vị trí

Bài này nằm cạnh Coin Change (LeetCode 322) trong series này, nhưng DP state về cơ bản khác nhau. Coin Change định nghĩa dp[i] trên các amount — một target vô hướng. LIS định nghĩa dp[i] trên các vị trí mảng — state phụ thuộc vào vị trí bạn đang ở trong input, không chỉ một con số đơn.

DP theo index-position với formulation "giá trị tốt nhất kết thúc ở đây" xuất hiện trong nhiều bài khác. LeetCode 152 (Maximum Product Subarray) theo dõi cả tích lớn nhất lẫn nhỏ nhất kết thúc tại mỗi index vì số âm có thể đảo dấu — đây là cùng ý tưởng lookback nhưng với hai giá trị theo dõi thay vì một. LeetCode 673 (Number of LIS) hỏi có bao nhiêu LIS phân biệt tồn tại — bạn mở rộng bảng DP với một mảng count song song, nên dp[i] trở thành cặp (length, count). LeetCode 354 (Russian Doll Envelopes) rút gọn về LIS sau khi sắp xếp envelopes theo width tăng dần và height giảm dần, rồi chạy LIS trên heights — phần khéo léo là sự rút gọn đó.

Cách binary search ở đây tổng quát hóa trực tiếp cho LeetCode 354: một khi bạn hiểu phiên bản O(n log n) binary search, Russian Doll Envelopes chỉ là một bước sort cách xa giải pháp tương tự.

Tôi sẽ ship DP O(n²) cho hầu hết ngữ cảnh phỏng vấn — code chỉ bốn dòng, logic tự giải thích, xử lý mọi edge case mà không có subtlety binary search. Phiên bản O(n log n) đáng biết vì patience-sorting invariant thực sự elegant, và trick bisect_left tương tự xuất hiện trong các bài khác mà việc duy trì cấu trúc được sắp xếp mở ra một complexity class tốt hơn.