当前位置:网站首页>LeetCode 1626. 无矛盾的最佳球队 每日一题
LeetCode 1626. 无矛盾的最佳球队 每日一题
2022-07-07 15:32:00 【@小红花】
问题描述
假设你是球队的经理。对于即将到来的锦标赛,你想组合一支总体得分最高的球队。球队的得分是球队中所有球员的分数 总和 。
然而,球队中的矛盾会限制球员的发挥,所以必须选出一支 没有矛盾 的球队。如果一名年龄较小球员的分数 严格大于 一名年龄较大的球员,则存在矛盾。同龄球员之间不会发生矛盾。
给你两个列表 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 <= 1000
scores.length == ages.length
1 <= scores[i] <= 106
1 <= ages[i] <= 1000来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/best-team-with-no-conflicts
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
Java
class Solution {
public int bestTeamScore(int[] scores, int[] ages) {
int n = scores.length;
int[][] player = new int[n][2];//年龄和分数
for(int i = 0;i < n;i++){
player[i][0] = ages[i];
player[i][1] = scores[i];
}
//排序
Arrays.sort(player,(a,b) -> a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]);
int[] dp = new int[n];
dp[0] = player[0][1];
int ans = dp[0];
for(int i = 1;i < n;i++){
dp[i] = player[i][1];
for(int j = 0;j < i;j++){
//不冲突的情况下
if(!(player[i][0] > player[j][0] && player[i][1] < player[j][1])){
dp[i] = Math.max(dp[i],dp[j] + player[i][1]);
}
}
ans = Math.max(ans,dp[i]);
}
return ans;
}
}
边栏推荐
猜你喜欢
随机推荐
面向接口编程
Temperature sensor chip used in temperature detector
The team of East China Normal University proposed the systematic molecular implementation of convolutional neural network with DNA regulation circuit
three. JS create cool snow effect
php 自带过滤和转义函数
【DesignMode】外观模式 (facade patterns)
【Vulnhub靶场】THALES:1
Cesium(3):ThirdParty/zip. js
How does laravel run composer dump autoload without emptying the classmap mapping relationship?
ATM system
使用JSON.stringify()去实现深拷贝,要小心哦,可能有巨坑
Statistical learning method -- perceptron
Opportunity interview experience summary
typescript ts 基础知识之类型声明
Interface oriented programming
Usage of config in laravel
Lowcode: four ways to help transportation companies enhance supply chain management
Master this promotion path and share interview materials
Three. JS series (1): API structure diagram-1
1亿单身男女“在线相亲”,撑起130亿IPO