Medium
673. Number of Longest Increasing Subsequence
arraydynamic-programmingbinary-indexed-treesegment-tree
解題說明
Number of Longest Increasing Subsequence
題目描述：給定一個未排序的整數陣列 nums，回傳其中最長遞增子序列（LIS）的個數。
解題思路：使用動態規劃，定義兩個陣列：
len[i]：以nums[i]結尾的最長遞增子序列長度。cnt[i]：以nums[i]結尾的最長遞增子序列個數。
對每個 i，遍歷所有 j < i：
- 若
nums[j] < nums[i]，可以接在j後面。 - 若
len[j] + 1 > len[i]，找到更長的子序列，更新len[i]並設cnt[i] = cnt[j]。 - 若
len[j] + 1 == len[i]，找到等長的子序列，cnt[i] += cnt[j]。
最後，統計所有 len[i] 等於全域最大長度的 cnt[i] 之和。
C++ 解法
複雜度分析
時間複雜度：O(n^2) — 雙層迴圈遍歷所有配對。
空間複雜度：O(n) — 兩個長度為 n 的輔助陣列。
虛擬碼
1. Initialize len[i] = 1, cnt[i] = 1 for all i
2. For i from 1 to n-1:
a. For j from 0 to i-1:
- If nums[j] < nums[i]:
- 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]
b. Update maxLen = max(maxLen, len[i])
3. Sum cnt[i] for all i where len[i] == maxLen
4. Return sum其他解法
線段樹 / BIT 優化：使用線段樹或樹狀陣列維護 (length, count) 的對映，對值域查詢最大長度及其計數，可將時間複雜度降至 O(n log n)。實作較複雜，適合 n 較大的場景。
Patience Sorting 變體：類似 LIS 的二分搜尋解法，但需要額外記錄每個位置的計數，實作更為複雜。
延伸思考
- 如何用線段樹將時間複雜度優化到 O(n log n)？
- 如果要求的是最長非遞減子序列的個數，需要修改哪些條件？
- 能否同時輸出所有最長遞增子序列本身（而非只是個數）？