1626. 无矛盾的最佳球队 - Kotlin 背包DP

Problem: 1626. 无矛盾的最佳球队

思路

参照题解思路

由题意可知，一个队伍中年龄较大的球员必定分数大于年龄较小的成员，换句话说，球队中年龄最大的球员也必然是分数最高的球员，我们可以按照年龄或者分数的任意一者对队伍中的球员排序，则此时这名球员即为最后一名球员

设为以第i个球员为最后一名球员时的全队分数，用数组记录下每个球员的年龄和分数，并对member按照升序排序(优先年龄，年龄相同时比较分数)

由于在加入队伍时，要求年龄和分数都必须大于等于最后一名球员，所以对member排序时，优先按照年龄还是优先按照分数是等价的，只是在加入队伍时需要判断的条件有所区别，这里假设优先按照年龄排序

由于我们对members按照年龄升序排序，只要我们顺序遍历members，那么球员的年龄必然是大于等于目前已知的最大球员的，我们只需要考虑球员的分数即可

当我们当前考虑的球员为第位球员时，令j遍历，已知中的最后一名球员年龄都必然小于等于第位球员，只需要保证最后一名球员的分数也小于等于第位球员，那么第位球员就可以加入该球队，此时球队的分数

对于所有情况取最大值即为第位球员为最后一名球员时的球队最大分数，即

考虑到边界情况，第位球员可以自己单成一队，即初始化为：

复杂度

时间复杂度:

空间复杂度:

Code

class Solution {
    fun bestTeamScore(scores: IntArray, ages: IntArray): Int {
        val members = Array(scores.size) { i -> intArrayOf(ages[i], scores[i]) }.sortedWith(compareBy({ it[0] }, { it[1] }))
        //sortWith { a, b -> if (a[0] != b[0]) a[0] - b[0] else a[1] - b[1] }这么写的话力扣的编译器会过不了
        val dp = IntArray(scores.size) { i -> members[i][1] }

        for (i in members.indices) {
            for (j in 0 until i) {
                if (members[i][1] >= members[j][1]) {
                    dp[i] = Math.max(dp[i], dp[j] + members[i][1])
                }
            }
        }
        return dp.max()!!
    }
}