Number of Longest Increasing Subsequence trong C++

Cho mảng số nguyên không sắp xếp. Tìm số lượng dãy con tăng dài nhất (LIS).

Ví dụ: [1,3,5,4,7] → output 2, vì có 2 LIS: [1,3,5,7] và [1,3,4,7].

Giải thuật (DP)

• n = nums.size(), mảng len và cnt kích thước n khởi tạo 1.
• lis = 1.
• Duyệt i=1..n-1, j=0..i-1:
  • Nếu nums[i] > nums[j]:
    • Nếu len[j]+1 > len[i]: len[i] = len[j]+1, cnt[i] = cnt[j].
    • Nếu len[j]+1 == len[i]: cnt[i] += cnt[j].
  • lis = max(lis, len[i]).
• Tổng cnt[i] với len[i] == lis.

Ví dụ code

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int findNumberOfLIS(vector<int>& nums) {
        int n = nums.size();
        vector<int> len(n,1), cnt(n,1);
        int lis = 1;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    if (len[j] + 1 > len[i]) {
                        len[i] = len[j] + 1;
                        cnt[i] = cnt[j];
                    } else if (len[j] + 1 == len[i]) {
                        cnt[i] += cnt[j];
                    }
                }
            }
            lis = max(lis, len[i]);
        }
        int ans = 0;
        for (int i = 0; i < n; i++) if (len[i] == lis) ans += cnt[i];
        return ans;
    }
};

int main() {
    Solution ob;
    vector<int> v = {1,3,5,4,7};
    cout << ob.findNumberOfLIS(v);
    return 0;
}

Input

[1,3,5,4,7]

Output

2