1626. Best Team with no Conflicts

解法已隱藏 — 先讀題目敘述、自己想想看，再點上方按鈕揭曉。

1626Best Team with no Conflicts1-D DPMedium1-D DP

給定球員的分數 scores 和年齡 ages，選出一支隊伍使總分最高，但不能有衝突：年齡較小的球員分數不能嚴格高於年齡較大的球員。

Example:

Input: scores = [4,5,6,5], ages = [2,1,2,1] Output: 16

Intuition

TIP

按年齡（及分數）排序後，問題轉化為求分數的最長非遞減子序列的最大和（LIS 變體）。

排序後，只需確保選出的球員分數也是非遞減的
等同於 LIS 問題，但目標是最大化分數總和而非長度
dp[i] = 以第 i 個球員結尾的最大總分

Approaches

1. Memoization (Top-Down DP) — O(n^2) / O(n)

Idea: 排序後，定義 f(i) = 以第 i 個球員結尾的最大總分，遞迴尋找前面所有合法 j 的最大值，加 memo
Time: O(n^2) - 每個狀態 O(n)，共 n 個狀態
Space: O(n) - memo + 遞迴堆疊

class Solution {
    fun bestTeamScore(scores: IntArray, ages: IntArray): Int {
        val n = scores.size
        val players = Array(n) { intArrayOf(ages[it], scores[it]) }
        players.sortWith(compareBy({ it[0] }, { it[1] }))

        val memo = IntArray(n) { -1 }
        fun dp(i: Int): Int {
            if (memo[i] != -1) return memo[i]
            var best = players[i][1]
            for (j in 0 until i) {
                if (players[j][1] <= players[i][1]) {
                    best = maxOf(best, dp(j) + players[i][1])
                }
            }
            memo[i] = best
            return best
        }
        var ans = 0
        for (i in 0 until n) ans = maxOf(ans, dp(i))
        return ans
    }
}

2. Bottom-Up DP O(n^2) — O(n^2) / O(n)

Idea: 排序後對每個球員，找前面所有分數 <= 它的球員，取最大總分
Time: O(n^2)
Space: O(n)

class Solution {
    fun bestTeamScore(scores: IntArray, ages: IntArray): Int {
        val n = scores.size
        val players = Array(n) { intArrayOf(ages[it], scores[it]) }
        players.sortWith(compareBy({ it[0] }, { it[1] }))

        val dp = IntArray(n)
        for (i in 0 until n) {
            dp[i] = players[i][1]
            for (j in 0 until i) {
                if (players[j][1] <= players[i][1]) {
                    dp[i] = maxOf(dp[i], dp[j] + players[i][1])
                }
            }
        }
        return dp.max()
    }
}

⭐ 3. BIT (Binary Indexed Tree) Optimization — O(n log M) / O(M)

Idea: 用 BIT 在分數值域上維護最大 dp 值，將查詢從 O(n) 降到 O(log M)
Time: O(n log M) 其中 M 為分數最大值
Space: O(M)

class Solution {
    fun bestTeamScore(scores: IntArray, ages: IntArray): Int {
        val n = scores.size
        val players = Array(n) { intArrayOf(ages[it], scores[it]) }
        players.sortWith(compareBy({ it[0] }, { it[1] }))

        val maxScore = scores.max()
        val bit = IntArray(maxScore + 2) // BIT，支援 prefix max query

        fun query(i: Int): Int {
            var idx = i; var res = 0
            while (idx > 0) { res = maxOf(res, bit[idx]); idx -= idx and (-idx) }
            return res
        }
        fun update(i: Int, v: Int) {
            var idx = i
            while (idx <= maxScore + 1) { bit[idx] = maxOf(bit[idx], v); idx += idx and (-idx) }
        }

        var ans = 0
        for (p in players) {
            val score = p[1]
            val best = query(score + 1) + score // +1 因為 BIT 是 1-indexed
            update(score + 1, best)
            ans = maxOf(ans, best)
        }
        return ans
    }
}

🔑 Takeaways

Pattern: 排序 + LIS 變體 — 多維度約束問題，排序消除一個維度後轉化為 LIS
Key trick: 按 (age, score) 排序後，只需保證分數非遞減即可避免衝突；BIT 可以將 LIS 類問題從 O(n^2) 優化到 O(n log n)

Intuition

Approaches

🔑 Takeaways

相關題目