1626.无矛盾的最佳球队

链接：1626.无矛盾的最佳球队
难度：Medium
标签：数组、动态规划、排序
简介：给你两个列表 scores 和 ages，其中每组 scores[i] 和 ages[i] 表示第 i 名球员的分数和年龄。请你返回 所有可能的无矛盾球队中得分最高那支的分数 。

题解 1 - cpp

• 编辑时间：2023-03-22
• 执行用时：452ms
• 内存消耗：18.4MB
• 编程语言：cpp
• 解法介绍：dp[i]表示以i为结尾时的最大分数。

class Solution {
public:
    int bestTeamScore(vector<int>& scores, vector<int>& ages) {
        int n = scores.size(), res = 0;
        vector<int> idx(n), dp(n, 0);
        for (int i = 0; i < n; i++) idx[i] = i;
        sort(idx.begin(), idx.end(), [&](auto &a, auto &b){
            return ages[a] != ages[b] ? ages[a] < ages[b] : scores[a] < scores[b];
        });
        for (int i = 0; i < n; i++) {
            for (int j = i - 1; j >= 0; j--) {
                if (ages[idx[i]] == ages[idx[j]] || ages[idx[i]] > ages[idx[j]] && scores[idx[i]] >= scores[idx[j]])
                    dp[i] = max(dp[i], dp[j]);
            }
            dp[i] += scores[idx[i]];
            res = max(res, dp[i]);
        }
        return res;
    }
};

题解 2 - python

• 编辑时间：2023-03-22
• 执行用时：2676ms
• 内存消耗：15.1MB
• 编程语言：python
• 解法介绍：同上。

class Solution:
    def bestTeamScore(self, scores: List[int], ages: List[int]) -> int:
        n, res = len(scores), 0
        l = sorted(zip(ages, scores))
        dp = [0] * n
        for i in range(n):
            for j in range(i-1, -1, -1):
                if l[i][0] == l[j][0] or (l[i][0] > l[j][0] and l[i][1] >= l[j][1]):
                    dp[i] = max(dp[i], dp[j])
            dp[i] += l[i][1]
            res = max(res, dp[i])
        return res

题解 3 - rust

• 编辑时间：2023-03-22
• 执行用时：44ms
• 内存消耗：2.1MB
• 编程语言：rust
• 解法介绍：同上。

impl Solution {
    pub fn best_team_score(scores: Vec<i32>, ages: Vec<i32>) -> i32 {
        let (n, mut res) = (scores.len(), 0);
        let mut idx = (0..n).collect::<Vec<usize>>();
        idx.sort_by(|a, b| {
            if ages[*a] != ages[*b] {
                ages[*a].cmp(&ages[*b])
            } else {
                scores[*a].cmp(&scores[*b])
            }
        });
        let mut dp = vec![0; n];
        for i in 0..n as i32 {
            for j in ((0i32)..=(i - 1)).rev() {
                let (i, j) = (i as usize, j as usize);
                if ages[idx[i]] == ages[idx[j]]
                    || ages[idx[i]] > ages[idx[j]] && scores[idx[i]] >= scores[idx[j]]
                {
                    dp[i] = dp[i].max(dp[j]);
                }
            }
            dp[i as usize] += scores[idx[i as usize]];
            res = res.max(dp[i as usize]);
        }
        res
    }
}