1. Chuỗi con tăng dài nhất (Longest Increasing Subsequence)

Bài toán yêu cầu tìm độ dài của chuỗi con tăng dài nhất từ một mảng số nguyên cho trước. Các phần tử trong chuỗi con không nhất thiết phải nằm liên tiếp nhau nhưng phải giữ nguyên thứ tự xuất hiện.

Giải thuật quy hoạch động:

Chúng ta định nghĩa dp[i] là độ dài của chuỗi con tăng dài nhất kết thúc tại chỉ số i. Để xác định giá trị của dp[i], ta cần xem xét tất cả các chỉ số j đứng trước i (0 ≤ j < i). Nếu phần tử tại i lớn hơn phần tử tại j, ta có thể kéo dài chuỗi con kết thúc tại j bằng cách thêm phần tử tại i vào.

Công thức truy hồi: dp[i] = max(dp[i], dp[j] + 1) với điều kiện nums[i] > nums[j].

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        if (n <= 1) return n;
        
        // Khởi tạo mảng dp với giá trị 1, vì mỗi phần tử đơn lẻ là một chuỗi con độ dài 1
        vector<int> dp(n, 1);
        int max_len = 0;
        
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
            if (dp[i] > max_len) max_len = dp[i];
        }
        
        // Trường hợp mảng chỉ có 1 phần tử hoặc tất cả giảm dần
        return max_len == 0 ? 1 : max_len;
    }
};

2. Chuỗi con tăng liên tục dài nhất (Longest Continuous Increasing Subsequence)

Khác với bài toán trên, ở đây các phần tử trong chuỗi con phải nằm liên tiếp nhau trong mảng gốc. Điều này làm đơn giản hóa bài toán vì trạng thái hiện tại chỉ phụ thuộc trực tiếp vào trạng thái ngay trước đó.

Giải pháp 1: Quy hoạch động

Nếu nums[i] > nums[i-1], độ dài chuỗi con tăng liên tục tại i sẽ bằng độ dài tại i-1 cộng thêm 1. Ngược lại, nó được reset về 1.

int findLengthOfLCIS(vector<int>& nums) {
    if (nums.empty()) return 0;
    vector<int> dp(nums.size(), 1);
    int result = 1;
    for (int i = 1; i < nums.size(); i++) {
        if (nums[i] > nums[i - 1]) {
            dp[i] = dp[i - 1] + 1;
        }
        result = max(result, dp[i]);
    }
    return result;
}

Giải pháp 2: Tối ưu không gian (Tham lam)

Vì dp[i] chỉ phụ thuộc vào dp[i-1], ta có thể thay thế mảng bằng một biến đếm duy nhất để tiết kiệm bộ nhớ.

int findLengthOfLCISOptimized(vector<int>& nums) {
    int n = nums.size();
    if (n == 0) return 0;
    
    int longest = 1;
    int current_streak = 1;
    
    for (int k = 1; k < n; k++) {
        if (nums[k] > nums[k-1]) {
            current_streak++;
        } else {
            current_streak = 1;
        }
        longest = max(longest, current_streak);
    }
    return longest;
}

3. Mảng con lặp lại dài nhất (Maximum Length of Repeated Subarray)

Cho hai mảng số nguyên, tìm độ dài lớn nhất của một mảng con xuất hiện trong cả hai mảng. Mảng con yêu cầu các phần tử phải liên tiếp.

Phân tích trạng thái:

Sử dụng mảng hai chiều dp[i][j] đại diện cho độ dài của mảng con chung dài nhất kết thúc tại nums1[i-1] và nums2[j-1]. Việc sử dụng i-1 và j-1 giúp xử lý lề mảng dễ dàng hơn mà không cần kiểm tra điều kiện biên phức tạp cho chỉ số 0.

Công thức chuyển trạng thái:

Nếu nums1[i-1] == nums2[j-1], thì dp[i][j] = dp[i-1][j-1] + 1. Nếu không bằng nhau, dp[i][j] sẽ bằng 0 vì mảng con yêu cầu tính liên tục.

class Solution {
public:
    int findLength(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size();
        int n = nums2.size();
        int maxLength = 0;
        
        // dp[i][j] lưu độ dài mảng con chung kết thúc tại nums1[i-1] và nums2[j-1]
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
        
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (nums1[i - 1] == nums2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                }
                if (dp[i][j] > maxLength) {
                    maxLength = dp[i][j];
                }
            }
        }
        
        return maxLength;
    }
};