Best Team With No Conflicts
给两个数组, 一个是score 一个age, 求在没有conflict的情况下的最大score. conflict是两个数组的数, 在同age下的score必须大小严格保持一致.
dp题. 两个可能: 选当前的人或者不选当前的人. 然后求最大的score.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
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; } } |