Cho một mảng các số nguyên không sắp xếp, hãy tìm số lượng dãy con tăng dần dài nhất.

Ví dụ 1:

Input: [1,3,5,4,7]
Output: 2
Giải thích: Hai dãy con tăng dần dài nhất là [1, 3, 4, 7] và [1, 3, 5, 7].

Ví dụ 2:

Input: [2,2,2,2,2]
Output: 5
Giải thích: Dãy con tăng dần dài nhất có độ dài 1, và có 5 phần tử như vậy, nên kết quả là 5.

Phân tích thuật toán:

Chúng ta sử dụng hai mảng phụ trợ:

• lengths[i]: lưu độ dài của dãy con tăng dần dài nhất kết thúc tại vị trí i.
• counts[i]: lưu số lượng dãy con tăng dần có độ dài bằng lengths[i] và kết thúc tại vị trí i.

Duyệt qua từng phần tử từ trái sang phải. Với mỗi nums[i], so sánh với tất cả các phần tử đứng trước nums[j] (với j < i). Nếu nums[j] < nums[i], ta có thể mở rộng dãy con kết thúc tại j bằng cách thêm nums[i].

Nếu lengths[j] + 1 > lengths[i] → cập nhật độ dài mới và gán số lần bằng số lần từ j.

Nếu lengths[j] + 1 == lengths[i] → cộng thêm số lần từ j vào counts[i] vì đã có nhiều cách tạo ra dãy con cùng độ dài.

Sau khi xử lý toàn bộ mảng, duyệt lại để tổng hợp số lượng dãy con có độ dài lớn nhất.

Mã nguồn:

C++

class Solution {
public:
    int findNumberOfLIS(vector<int>& nums) {
        vector<int> seqLength(nums.size(), 1);
        vector<int> sequenceCount(nums.size(), 1);

        for (int i = 1; i < nums.size(); ++i) {
            for (int j = 0; j < i; ++j) {
                if (nums[j] >= nums[i]) continue;

                if (seqLength[j] + 1 > seqLength[i]) {
                    seqLength[i] = seqLength[j] + 1;
                    sequenceCount[i] = sequenceCount[j];
                } else if (seqLength[j] + 1 == seqLength[i]) {
                    sequenceCount[i] += sequenceCount[j];
                }
            }
        }

        int maxLength = 0;
        int totalWays = 0;
        for (int i = 0; i < seqLength.size(); ++i) {
            if (seqLength[i] > maxLength) {
                maxLength = seqLength[i];
                totalWays = sequenceCount[i];
            } else if (seqLength[i] == maxLength) {
                totalWays += sequenceCount[i];
            }
        }

        return totalWays;
    }
};

Java

class Solution {
    public int findNumberOfLIS(int[] nums) {
        if (nums.length == 0) return 0;

        int[] maxLenAt = new int[nums.length];
        int[] countAt = new int[nums.length];

        int overallMaxLen = 1;

        for (int i = 0; i < nums.length; ++i) {
            maxLenAt[i] = 1;
            countAt[i] = 1;

            for (int j = 0; j < i; ++j) {
                if (nums[i] <= nums[j]) continue;

                if (maxLenAt[j] + 1 > maxLenAt[i]) {
                    maxLenAt[i] = maxLenAt[j] + 1;
                    countAt[i] = countAt[j];
                } else if (maxLenAt[j] + 1 == maxLenAt[i]) {
                    countAt[i] += countAt[j];
                }
            }

            overallMaxLen = Math.max(overallMaxLen, maxLenAt[i]);
        }

        int result = 0;
        for (int i = 0; i < maxLenAt.length; ++i) {
            if (maxLenAt[i] == overallMaxLen) {
                result += countAt[i];
            }
        }

        return result;
    }
}