Number of Longest Increasing Subsequence ใน C++

โจทย์: Number of Longest Increasing Subsequence

ให้อาร์เรย์จำนวนเต็ม nums ไม่เรียงลำดับ ต้องหา จำนวนของ Longest Increasing Subsequence (LIS) ที่มีความยาวสูงสุด

ตัวอย่าง: nums = [1, 3, 5, 4, 7]

LIS ความยาว 4 มี 2 ชุด: [1,3,5,7] และ [1,3,4,7] → ผลลัพธ์: 2

อัลกอริทึม: DP O(n²)

สำหรับแต่ละ index i เก็บ:

• len[i] = ความยาว LIS ที่จบที่ index i
• cnt[i] = จำนวน LIS ที่จบที่ index i และมีความยาว = len[i]

Initialization:

len[i] = 1, cnt[i] = 1 สำหรับทุก i (ตัวเองเป็น LIS ยาว 1)

Transition:

สำหรับแต่ละ i จาก 1 ถึง n-1, วน j จาก 0 ถึง i-1:

• หาก nums[i] > nums[j] (สามารถต่อท้ายได้):
  • หาก len[j] + 1 > len[i]: พบ LIS ยาวกว่า → len[i] = len[j] + 1, cnt[i] = cnt[j]
  • หาก len[j] + 1 == len[i]: พบ LIS ยาวเท่าเดิม → cnt[i] += cnt[j]

ผลลัพธ์:

max_len = max(len[i]) แล้วรวม cnt[i] ของทุก i ที่ len[i] == max_len

ตัวอย่างโค้ด C++

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

class Solution {
public:
    int findNumberOfLIS(vector<int>& nums) {
        int n = nums.size();
        if (n == 0) return 0;
        
        vector<int> len(n, 1), cnt(n, 1);
        int max_len = 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];
                    }
                }
            }
            max_len = max(max_len, len[i]);
        }
        
        int ans = 0;
        for (int i = 0; i < n; i++) {
            if (len[i] == max_len) ans += cnt[i];
        }
        return ans;
    }
};

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

Input

[1,3,5,4,7]

Output

2

ความซับซ้อน (Complexity)

• เวลา: O(n²)
• พื้นที่: O(n)

หมายเหตุ: สำหรับ n ใหญ่ (n ≤ 2000) O(n²) ยอมรับได้ หาก n ใหญ่มาก (10⁵) ต้องใช้ Segment Tree / Fenwick Tree + Coordinate Compression ได้ O(n log n)