題目描述:
給定 scores 和 ages 兩個陣列,代表球員的分數和年齡。選出一個團隊使得總分最高,且不存在衝突:若年輕球員的分數嚴格大於年長球員,則產生衝突。同齡球員之間不會衝突。
解題思路: 此問題等價於「最長遞增子序列」的變形(Longest Increasing Subsequence, LIS 的加權版本)。
dp[i] 表示以第 i 個球員結尾的最大團隊總分。對於每個 i,遍歷 j < i,若 scores[j] <= scores[i],則 dp[i] = max(dp[i], dp[j] + scores[i])。dp[i] 的最大值。時間複雜度: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 邏輯。時空複雜度不變,但寫法較為直觀。