Question

1626. 无矛盾的最佳球队

English Version

题目描述

假设你是球队的经理。对于即将到来的锦标赛，你想组合一支总体得分最高的球队。球队的得分是球队中所有球员的分数 总和 。

然而，球队中的矛盾会限制球员的发挥，所以必须选出一支 没有矛盾 的球队。如果一名年龄较小球员的分数 严格大于 一名年龄较大的球员，则存在矛盾。同龄球员之间不会发生矛盾。

给你两个列表 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

解法

方法一：排序 + 动态规划

我们可以将球员按照分数从小到大排序，如果分数相同，则按照年龄从小到大排序。

接下来，使用动态规划求解。

我们定义 $f[i]$ 表示以排序后的第 $i$ 个球员作为最后一个球员的最大得分，那么答案就是 $\max_{0 \leq i < n} f[i]$。

对于 $f[i]$，我们可以枚举 $0 \leq j \lt i$，如果第 $i$ 个球员的年龄大于等于第 $j$ 个球员的年龄，则 $f[i]$ 可以从 $f[j]$ 转移而来，转移方程为 $f[i] = \max(f[i], f[j])$。然后我们将第 $i$ 个球员的分数加到 $f[i]$ 中，即 $f[i] += scores[i]$。

最后，我们返回 $\max_{0 \leq i < n} f[i]$ 即可。

时间复杂度 $O(n^2)$，空间复杂度 $O(n)$。其中 $n$ 为球员的数量。

class Solution:
  def bestTeamScore(self, scores: List[int], ages: List[int]) -> int:
    arr = sorted(zip(scores, ages))
    n = len(arr)
    f = [0] * n
    for i, (score, age) in enumerate(arr):
      for j in range(i):
        if age >= arr[j][1]:
          f[i] = max(f[i], f[j])
      f[i] += score
    return max(f)

class Solution {
  public int bestTeamScore(int[] scores, int[] ages) {
    int n = ages.length;
    int[][] arr = new int[n][2];
    for (int i = 0; i < n; ++i) {
      arr[i] = new int[] {scores[i], ages[i]};
    }
    Arrays.sort(arr, (a, b) -> a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]);
    int[] f = new int[n];
    int ans = 0;
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < i; ++j) {
        if (arr[i][1] >= arr[j][1]) {
          f[i] = Math.max(f[i], f[j]);
        }
      }
      f[i] += arr[i][0];
      ans = Math.max(ans, f[i]);
    }
    return ans;
  }
}

class Solution {
public:
  int bestTeamScore(vector<int>& scores, vector<int>& ages) {
    int n = ages.size();
    vector<pair<int, int>> arr(n);
    for (int i = 0; i < n; ++i) {
      arr[i] = {scores[i], ages[i]};
    }
    sort(arr.begin(), arr.end());
    vector<int> f(n);
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < i; ++j) {
        if (arr[i].second >= arr[j].second) {
          f[i] = max(f[i], f[j]);
        }
      }
      f[i] += arr[i].first;
    }
    return *max_element(f.begin(), f.end());
  }
};

func bestTeamScore(scores []int, ages []int) int {
  n := len(ages)
  arr := make([][2]int, n)
  for i := range ages {
    arr[i] = [2]int{scores[i], ages[i]}
  }
  sort.Slice(arr, func(i, j int) bool {
    a, b := arr[i], arr[j]
    return a[0] < b[0] || a[0] == b[0] && a[1] < b[1]
  })
  f := make([]int, n)
  for i := range arr {
    for j := 0; j < i; j++ {
      if arr[i][1] >= arr[j][1] {
        f[i] = max(f[i], f[j])
      }
    }
    f[i] += arr[i][0]
  }
  return slices.Max(f)
}

function bestTeamScore(scores: number[], ages: number[]): number {
  const arr = ages.map((age, i) => [age, scores[i]]);
  arr.sort((a, b) => (a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]));
  const n = arr.length;
  const f = new Array(n).fill(0);
  for (let i = 0; i < n; ++i) {
    for (let j = 0; j < i; ++j) {
      if (arr[i][1] >= arr[j][1]) {
        f[i] = Math.max(f[i], f[j]);
      }
    }
    f[i] += arr[i][1];
  }
  return Math.max(...f);
}

/**
 * @param {number[]} scores
 * @param {number[]} ages
 * @return {number}
 */
var bestTeamScore = function (scores, ages) {
  const arr = ages.map((age, i) => [age, scores[i]]);
  arr.sort((a, b) => (a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]));
  const n = arr.length;
  const f = new Array(n).fill(0);
  for (let i = 0; i < n; ++i) {
    for (let j = 0; j < i; ++j) {
      if (arr[i][1] >= arr[j][1]) {
        f[i] = Math.max(f[i], f[j]);
      }
    }
    f[i] += arr[i][1];
  }
  return Math.max(...f);
};

方法二：排序 + 树状数组

与方法一类似，我们可以将球员按照分数从小到大排序，如果分数相同，则按照年龄从小到大排序。

接下来，我们使用树状数组维护不超过当前球员年龄的球员的最大得分。每一次，我们只需要在 $O(\log m)$ 的时间内找出不超过当前球员年龄的球员的最大得分，然后将当前球员的分数加到该得分上，即可更新当前球员年龄的最大得分。

最后，我们返回得分的最大值即可。

时间复杂度 $O(n \times (\log n + \log m))$，空间复杂度 $O(n + m)$。其中 $n$ 和 $m$ 分别为球员的数量和球员的年龄的最大值。

class BinaryIndexedTree:
  def __init__(self, n):
    self.n = n
    self.c = [0] * (n + 1)

  def update(self, x, val):
    while x <= self.n:
      self.c[x] = max(self.c[x], val)
      x += x & -x

  def query(self, x):
    s = 0
    while x:
      s = max(s, self.c[x])
      x -= x & -x
    return s


class Solution:
  def bestTeamScore(self, scores: List[int], ages: List[int]) -> int:
    m = max(ages)
    tree = BinaryIndexedTree(m)
    for score, age in sorted(zip(scores, ages)):
      tree.update(age, score + tree.query(age))
    return tree.query(m)

class BinaryIndexedTree {
  private int n;
  private int[] c;

  public BinaryIndexedTree(int n) {
    this.n = n;
    c = new int[n + 1];
  }

  public void update(int x, int val) {
    while (x <= n) {
      c[x] = Math.max(c[x], val);
      x += x & -x;
    }
  }

  public int query(int x) {
    int s = 0;
    while (x > 0) {
      s = Math.max(s, c[x]);
      x -= x & -x;
    }
    return s;
  }
}

class Solution {
  public int bestTeamScore(int[] scores, int[] ages) {
    int n = ages.length;
    int[][] arr = new int[n][2];
    for (int i = 0; i < n; ++i) {
      arr[i] = new int[] {scores[i], ages[i]};
    }
    Arrays.sort(arr, (a, b) -> a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]);
    int m = 0;
    for (int age : ages) {
      m = Math.max(m, age);
    }
    BinaryIndexedTree tree = new BinaryIndexedTree(m);
    for (int[] x : arr) {
      tree.update(x[1], x[0] + tree.query(x[1]));
    }
    return tree.query(m);
  }
}

class BinaryIndexedTree {
public:
  BinaryIndexedTree(int _n)
    : n(_n)
    , c(_n + 1) {}

  void update(int x, int val) {
    while (x <= n) {
      c[x] = max(c[x], val);
      x += x & -x;
    }
  }

  int query(int x) {
    int s = 0;
    while (x) {
      s = max(s, c[x]);
      x -= x & -x;
    }
    return s;
  }

private:
  int n;
  vector<int> c;
};

class Solution {
public:
  int bestTeamScore(vector<int>& scores, vector<int>& ages) {
    int n = ages.size();
    vector<pair<int, int>> arr(n);
    for (int i = 0; i < n; ++i) {
      arr[i] = {scores[i], ages[i]};
    }
    sort(arr.begin(), arr.end());
    int m = *max_element(ages.begin(), ages.end());
    BinaryIndexedTree tree(m);
    for (auto& [score, age] : arr) {
      tree.update(age, score + tree.query(age));
    }
    return tree.query(m);
  }
};

type BinaryIndexedTree struct {
  n int
  c []int
}

func newBinaryIndexedTree(n int) *BinaryIndexedTree {
  c := make([]int, n+1)
  return &BinaryIndexedTree{n, c}
}

func (this *BinaryIndexedTree) update(x, val int) {
  for x <= this.n {
    this.c[x] = max(this.c[x], val)
    x += x & -x
  }
}

func (this *BinaryIndexedTree) query(x int) int {
  s := 0
  for x > 0 {
    s = max(s, this.c[x])
    x -= x & -x
  }
  return s
}

func bestTeamScore(scores []int, ages []int) int {
  n := len(ages)
  arr := make([][2]int, n)
  m := 0
  for i, age := range ages {
    m = max(m, age)
    arr[i] = [2]int{scores[i], age}
  }
  sort.Slice(arr, func(i, j int) bool {
    a, b := arr[i], arr[j]
    return a[0] < b[0] || a[0] == b[0] && a[1] < b[1]
  })
  tree := newBinaryIndexedTree(m)
  for _, x := range arr {
    tree.update(x[1], x[0]+tree.query(x[1]))
  }
  return tree.query(m)
}