Best Team With No Conflicts
给两个数组, 一个是score 一个age, 求在没有conflict的情况下的最大score. conflict是两个数组的数, 在同age下的score必须大小严格保持一致.
dp题. 两个可能: 选当前的人或者不选当前的人. 然后求最大的score.
class Solution {
class Pair{
int s;
int a;
Pair(int s, int a) {
this.s = s;
this.a = a;
}
}
public int bestTeamScore(int[] scores, int[] ages) {
int n = scores.length;
Pair[] pairs = new Pair[n];
for(int i = 0; i < n; i++) {
pairs[i] = new Pair(scores[i], ages[i]);
}
Arrays.sort(pairs, (a, b) -> (a.a == b.a ? a.s - b.s : a.a - b.a));
int[] dp = new int[n];
//init dp
for(int i = 0; i < n; i++) {
dp[i] = pairs[i].s;
}
// dp[i] the max score UNTILL player i which must include the player i
int res = 0;
for(int i = 0; i < n; i++) {
for(int j = 0; j < i; j++) {
if(pairs[i].s >= pairs[j].s)
dp[i] = Math.max(dp[i], dp[j] + pairs[i].s);
}
res = Math.max(res, dp[i]);
}
return res;
}
}