1626. Best Team with no Conflicts

Medium

Description

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

Example:

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

Intuition#

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

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

Approaches#

1: DP O(n^2)#

概念: 排序後對每個球員，找前面所有分數 <= 它的球員，取最大總分
時間複雜度: O(n^2)
空間複雜度: 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()
    }
}

⭐2: BIT (Binary Indexed Tree) Optimization#

概念: 用 BIT 在分數值域上維護最大 dp 值，將查詢從 O(n) 降到 O(log M)
時間複雜度: O(n log M) 其中 M 為分數最大值
空間複雜度: 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
關鍵技巧: 按 (age, score) 排序後，只需保證分數非遞減即可避免衝突；BIT 可以將 LIS 類問題從 O(n^2) 優化到 O(n log n)