scores数组中是每个队员的得分,ages数组中为对应队员的年龄,
现在要从这个队里挑选出一些队员,使总得分最高,
挑选时年龄大的要比年龄小的score更高(严格大于),才不会产生冲突。
返回最高的得分。
思路:
因为年龄大的分数不能低于年龄小的,存在一个比较的过程,
所以需要排序,按年龄从小到大排序,这样就从score-age的二维降到了只需要考虑score的一维。
选出尽可能多的队员,而且满足score是升序的(年龄已经升序排列),
所以等同于leetcode 300.最长递增子序列.
所以,按照最长递增子序列的DP来做。
当遍历到 i 时,和前面所有的元素(j = 0 ~ i-1)比较,当scores[i] >= scores[ j ] 时(注意是>=),
说明满足score升序的条件,这时dp[i] = max(dp[i], dp[ j ] + scores[i]), dp[ i ]的初始值为scores[i], 即前面score如果都不要了,就以现在的score为初始值。
(注意这里不是子序列的长度+1, 而是要加上score[ i ])
同时更新score总和的最大值。
还要注意排序时,当age相同时,score要按从小到大的顺序排列,这样才满足递增序列的条件。
class Solution {public int bestTeamScore(int[] scores, int[] ages) {int n = scores.length;Member[] members = new Member[n];int[] dp = new int[n];int res = 0;for(int i = 0; i < n; i++) {members[i] = new Member(scores[i], ages[i]);}Arrays.sort(members, (a, b)->(a.age==b.age?a.score-b.score:a.age-b.age));for(int i = 0; i < n; i++) {dp[i] = members[i].score;for(int j = i-1; j >= 0; j--) {if(members[i].score >= members[j].score) {dp[i] = Math.max(dp[i], dp[j] + members[i].score);}}res = Math.max(res, dp[i]);}return res;}
}class Member{int score = 0;int age = 0;public Member(int score, int age) {this.score = score;this.age = age;}
}