Mô tả bài toán

Cho một mảng số nguyên, tìm độ dài của dãy con tăng nghiêm ngặt dài nhất. Dãy con được hình thành bằng cách xóa phần tử nhưng giữ nguyên thứ tự các phần tử còn lại.

Ví dụ

Nhập: [10,9,2,5,3,7,101,18]
Kết quả: 4 (dãy con [2,3,7,101])

Nhập: [0,1,0,3,2,3]
Kết quả: 4

Nhập: [7,7,7,7,7,7,7]
Kết quả: 1

Ràng buộc

• 1 ≤ độ dài mảng ≤ 2500
• -10⁴ ≤ giá trị phần tử ≤ 10⁴

Phương pháp giải

1. Quy hoạch động

Ý tưởng: Sử dụng mảng dp lưu độ dài dãy tăng dài nhất kết thúc tại mỗi vị trí.

• Khởi tạo mảng dp giá trị 1
• Duyệt từ trái sang phải, với mỗi phần tử kiểm tra các phần tử trước đó
• Nếu phần tử hiện tại lớn hơn phần tử trước, cập nhật dp[i] = max(dp[i], dp[j] + 1)
• Độ phức tạp: O(n²)

2. Tham lam kết hợp Tìm kiếm nhị phân

Ý tưởng: Duy trì mảng minEnds lưu giá trị kết thúc nhỏ nhất của dãy con độ dài i+1.

• Với mỗi phần tử, sử dụng tìm kiếm nhị phân để xác định vị trí chèn
• Thay thế phần tử đầu tiên ≥ giá trị hiện tại
• Nếu lớn hơn tất cả, mở rộng dãy
• Độ phức tạp: O(n log n)

Triển khai mã

C#

// Quy hoạch động
public int TimDoDaiDayConTang(int[] arr) {
    if (arr == null || arr.Length == 0) return 0;
    
    int[] dp = new int[arr.Length];
    int maxLen = 1;
    for (int i = 0; i < arr.Length; i++) {
        dp[i] = 1;
        for (int j = 0; j < i; j++) {
            if (arr[i] > arr[j]) 
                dp[i] = Math.Max(dp[i], dp[j] + 1);
        }
        maxLen = Math.Max(maxLen, dp[i]);
    }
    return maxLen;
}

// Tham lam + Nhị phân
public int TimDoDaiDayConTangNangCao(int[] arr) {
    if (arr == null || arr.Length == 0) return 0;
    
    int[] minEnds = new int[arr.Length];
    int len = 0;
    
    foreach (int x in arr) {
        int low = 0, high = len;
        while (low < high) {
            int mid = low + (high - low) / 2;
            if (minEnds[mid] < x) low = mid + 1;
            else high = mid;
        }
        minEnds[low] = x;
        if (low == len) len++;
    }
    return len;
}

Python

# Quy hoạch động
def tim_do_dai_day_tang(self, arr: List[int]) -> int:
    if not arr: return 0
    
    dp = [1] * len(arr)
    max_len = 1
    
    for i in range(1, len(arr)):
        for j in range(i):
            if arr[i] > arr[j]:
                dp[i] = max(dp[i], dp[j] + 1)
        max_len = max(max_len, dp[i])
    
    return max_len

# Tham lam + Nhị phân
def tim_do_dai_day_tang_nang_cao(self, arr: List[int]) -> int:
    if not arr: return 0
    
    min_ends = []
    
    for x in arr:
        if not min_ends or x > min_ends[-1]:
            min_ends.append(x)
        else:
            left, right = 0, len(min_ends)
            while left < right:
                mid = (left + right) // 2
                if min_ends[mid] < x:
                    left = mid + 1
                else:
                    right = mid
            min_ends[left] = x
    
    return len(min_ends)

C++

// Quy hoạch động
int timDoDaiDayTang(vector<int>& arr) {
    if (arr.empty()) return 0;
    
    vector<int> dp(arr.size(), 1);
    int maxLen = 1;
    
    for (int i = 1; i < arr.size(); i++) {
        for (int j = 0; j < i; j++) {
            if (arr[i] > arr[j])
                dp[i] = max(dp[i], dp[j] + 1);
        }
        maxLen = max(maxLen, dp[i]);
    }
    return maxLen;
}

// Tham lam + Nhị phân
int timDoDaiDayTangCaiTien(vector<int>& arr) {
    if (arr.empty()) return 0;
    
    vector<int> minEnds;
    
    for (int x : arr) {
        auto pos = lower_bound(minEnds.begin(), minEnds.end(), x);
        if (pos == minEnds.end())
            minEnds.push_back(x);
        else
            *pos = x;
    }
    return minEnds.size();
}

Kết quả thực thi

So sánh giải pháp

Lỗi thường gặp

• Không xử lý mảng rỗng
• Sai khởi tạo mảng dp
• Lỗi biên trong tìm kiếm nhị phân
• Cập nhật độ dài tối đa sai vị trí

Bài toán liên quan

• Đếm số dãy con tăng dài nhất (LeetCode 673)
• Xếp envelope Nga (LeetCode 354)
• Dãy con tăng liên tiếp dài nhất (LeetCode 674)