解題說明
Best Team With No Conflicts
題目描述：
給定 scores 和 ages 兩個陣列，代表球員的分數和年齡。選出一個團隊使得總分最高，且不存在衝突：若年輕球員的分數嚴格大於年長球員，則產生衝突。同齡球員之間不會衝突。
解題思路： 此問題等價於「最長遞增子序列」的變形（Longest Increasing Subsequence, LIS 的加權版本）。
- 將所有球員按年齡排序，年齡相同時按分數排序。
- 排序後，問題轉化為：選出一個子序列使得分數也是非遞減的（保證不衝突），並最大化所選球員的分數之和。
- 用 DP：
dp[i]表示以第 i 個球員結尾的最大團隊總分。對於每個 i，遍歷 j < i，若scores[j] <= scores[i]，則dp[i] = max(dp[i], dp[j] + scores[i])。 - 答案為所有
dp[i]的最大值。
C++ 解法
複雜度分析
時間複雜度：O(n²) — 排序 O(n log n) + 雙重迴圈 DP O(n²)，以 DP 為主。
空間複雜度：O(n) — DP 陣列和排序用的配對陣列各需 O(n)。
虛擬碼
1. Create array of (age, score) pairs from input
2. Sort pairs by age ascending, then score ascending
3. Create dp array of size n
4. For each player i from 0 to n-1:
a. dp[i] = players[i].score (just pick self)
b. For each player j from 0 to i-1:
- If players[j].score <= players[i].score:
dp[i] = max(dp[i], dp[j] + players[i].score)
5. Return max of all dp[i]其他解法
BIT/樹狀陣列優化 O(n log M)：對分數做離散化後，用 Binary Indexed Tree 維護前綴最大值，將內層迴圈從 O(n) 降為 O(log M)，其中 M 為分數值域。適合 n 較大的場景。
記憶化搜索：以遞迴 + 備忘錄的方式實現相同的 DP 邏輯。時空複雜度不變，但寫法較為直觀。
延伸思考
- 如果允許最多 k 個衝突，問題該如何修改 DP 狀態？
- 能否將此問題建模為 DAG 上的最長路徑問題？
- 如果球員數量非常大（n = 10⁵），O(n²) 不夠快，如何用 BIT 優化到 O(n log n)？