Leetcode 1626. Best Team With No Conflicts

[Woodyiiiiiii]

这是2023/01/31的每日一题。我花了挺长时间加一点提示(确定是DP)才想出来。一开始我注意到允许O(n^2)时间复杂度，还想用排序+循环死方法得出，但显然没有利用好条件，这样的思路明显是错的，所以花了大把无用的时间。

题意中最大的难点是如何避免conflicts——年纪小的players不允许有大于比他年纪大的players的分数。

注意的是：

1. 可以任意选择可选的players(subsequences/排序/...)
2. 返回最大分数(想到二分/DP/排序/堆/...)

那么可以推导出一个结论：满足条件的所有的teams，其中players的scores序列一定是non-decreasing的。

就可以推导出，这道题的思路是Sorting/DP。

class Solution {
    public int bestTeamScore(int[] scores, int[] ages) {
        int n = scores.length;
        int[][] arr = new int[n][2];
        for (int i = 0; i < n; ++i) {
            arr[i][0] = ages[i];
            arr[i][1] = scores[i];
        }
        Arrays.sort(arr, (o1, o2) -> {
            if (o1[0] == o2[0]) {
                return o1[1] - o2[1];
            }
            return o1[0] - o2[0];
        });

        int ans = 0;
        int[] dp = new int[n];
        for (int i = 0; i < n; ++i) {
            dp[i] = arr[i][1];
            for (int j = 0; j < i; ++j) {
                if (arr[j][1] <= arr[i][1]) {
                    dp[i] = Math.max(dp[i], dp[j] + arr[i][1]);
                }
            }
            ans = Math.max(ans, dp[i]);
        }
        return ans;
    }
}

---

• 1626. Best Team With No Conflicts