class Solution {
public:
int bestTeamScore(vector<int>& scores, vector<int>& ages) {
}
};
1626. 无矛盾的最佳球队
假设你是球队的经理。对于即将到来的锦标赛，你想组合一支总体得分最高的球队。球队的得分是球队中所有球员的分数 总和 。
然而，球队中的矛盾会限制球员的发挥，所以必须选出一支 没有矛盾 的球队。如果一名年龄较小球员的分数 严格大于 一名年龄较大的球员，则存在矛盾。同龄球员之间不会发生矛盾。
给你两个列表 scores 和 ages，其中每组 scores[i] 和 ages[i] 表示第 i 名球员的分数和年龄。请你返回 所有可能的无矛盾球队中得分最高那支的分数 。
示例 1：
输入：scores = [1,3,5,10,15], ages = [1,2,3,4,5] 输出：34 解释：你可以选中所有球员。
示例 2：
输入：scores = [4,5,6,5], ages = [2,1,2,1] 输出：16 解释：最佳的选择是后 3 名球员。注意，你可以选中多个同龄球员。
示例 3：
输入：scores = [1,2,3,5], ages = [8,9,10,1] 输出：6 解释：最佳的选择是前 3 名球员。
提示：
1 <= scores.length, ages.length <= 1000scores.length == ages.length1 <= scores[i] <= 1061 <= ages[i] <= 1000原站题解
java 解法, 执行用时: 12 ms, 内存消耗: 41.4 MB, 提交时间: 2023-03-22 09:14:40
class Solution {
int maxAge;
int[] t;
int[][] people;
public int bestTeamScore(int[] scores, int[] ages) {
maxAge = Arrays.stream(ages).max().getAsInt();
t = new int[maxAge + 1];
int res = 0;
int n = scores.length;
people = new int[n][2];
for (int i = 0; i < n; ++i) {
people[i] = new int[]{scores[i], ages[i]};
}
Arrays.sort(people, (a, b) -> a[0] != b[0] ? a[0] - b[0] : a[1] - b[1]);
for (int i = 0; i < n; ++i) {
int score = people[i][0], age = people[i][1], cur = score + query(age);
update(age, cur);
res = Math.max(res, cur);
}
return res;
}
public int lowbit(int x) {
return x & (-x);
}
public void update(int i, int val) {
for (; i <= maxAge; i += lowbit(i)) {
t[i] = Math.max(t[i], val);
}
}
public int query(int i) {
int ret = 0;
for (; i > 0; i -= lowbit(i)) {
ret = Math.max(ret, t[i]);
}
return ret;
}
}
java 解法, 执行用时: 40 ms, 内存消耗: 41.6 MB, 提交时间: 2023-03-22 09:14:01
class Solution {
public int bestTeamScore(int[] scores, int[] ages) {
int n = scores.length;
int[][] people = new int[n][2];
for (int i = 0; i < n; ++i) {
people[i] = new int[]{scores[i], ages[i]};
}
Arrays.sort(people, (a, b) -> a[0] != b[0] ? a[0] - b[0] : a[1] - b[1]);
int[] dp = new int[n];
int res = 0;
for (int i = 0; i < n; ++i) {
for (int j = i - 1; j >= 0; --j) {
if (people[j][1] <= people[i][1]) {
dp[i] = Math.max(dp[i], dp[j]);
}
}
dp[i] += people[i][0];
res = Math.max(res, dp[i]);
}
return res;
}
}
golang 解法, 执行用时: 48 ms, 内存消耗: 6.6 MB, 提交时间: 2023-03-22 09:13:36
func bestTeamScore(scores []int, ages []int) int {
n := len(scores)
people := make([][]int, n)
for i := range scores {
people[i] = []int{scores[i], ages[i]}
}
sort.Slice(people, func(i, j int) bool {
if people[i][0] < people[j][0] {
return true
} else if people[i][0] > people[j][0] {
return false
}
return people[i][1] < people[j][1]
})
dp := make([]int, n)
res := 0
for i := 0; i < n; i++ {
for j := 0; j < i; j++ {
if people[j][1] <= people[i][1] {
dp[i] = max(dp[i], dp[j])
}
}
dp[i] += people[i][0]
res = max(res, dp[i])
}
return res
}
func max(a, b int) int {
if b > a {
return b
}
return a
}
javascript 解法, 执行用时: 144 ms, 内存消耗: 47.2 MB, 提交时间: 2023-03-22 09:13:23
/**
* @param {number[]} scores
* @param {number[]} ages
* @return {number}
*/
var bestTeamScore = function(scores, ages) {
const n = scores.length;
const people = new Array(n).fill(0).map(() => new Array(2).fill(0));
for (let i = 0; i < n; ++i) {
people[i] = [scores[i], ages[i]];
}
people.sort((a, b) => a[0] !== b[0] ? a[0] - b[0] : a[1] - b[1]);
const dp = new Array(n).fill(0);
let res = 0;
for (let i = 0; i < n; ++i) {
for (let j = i - 1; j >= 0; --j) {
if (people[j][1] <= people[i][1]) {
dp[i] = Math.max(dp[i], dp[j]);
}
}
dp[i] += people[i][0];
res = Math.max(res, dp[i]);
}
return res;
};
python3 解法, 执行用时: 1512 ms, 内存消耗: 15.3 MB, 提交时间: 2023-03-22 09:12:54
class Solution:
def bestTeamScore(self, scores: List[int], ages: List[int]) -> int:
arr = list(sorted(zip(ages, scores)))
dp = [a[1] for a in arr]
for i in range(len(arr)):
for j in range(i):
if arr[i][1] >= arr[j][1]:
dp[i] = max(dp[i], dp[j] + arr[i][1])
return max(dp)
python3 解法, 执行用时: 1552 ms, 内存消耗: 15.2 MB, 提交时间: 2023-03-22 09:12:32
class Solution:
def bestTeamScore(self, scores: List[int], ages: List[int]) -> int:
n = len(scores)
# 按年龄递增排序，年龄相同的按分数递增排序
arr = list(zip(ages, scores))
arr.sort(key=lambda x : (x[0], x[1]))
dp = [arr[i][1] for i in range(n)]
for i in range(n):
for j in range(i):
if arr[i][1] >= arr[j][1]:
dp[i] = max(dp[i], dp[j]+arr[i][1])
return max(dp)
python3 解法, 执行用时: 5068 ms, 内存消耗: 76.6 MB, 提交时间: 2023-03-22 09:11:47
# dfs 记忆化搜索
class Solution:
def bestTeamScore(self, scores: List[int], ages: List[int]) -> int:
def dfs(u: int, v: int) -> int:
if v != -1 and mp[u][v] != -1:
return mp[u][v]
if u == n:
return 0
res = dfs(u+1, v)
if v==-1 or g[u][1]>=g[v][1]:
res = max(res, dfs(u+1, u)+g[u][1])
mp[u][v] = res
return res
n = len(scores)
mp = [[-1 for _ in range(n+1)] for _ in range(n+1)]
g = [[ages[_], scores[_]] for _ in range(n)]
g.sort()
return dfs(0, -1)