1626.无矛盾的最佳球队.md

1626.无矛盾的最佳球队

/*
 * @lc app=leetcode.cn id=1626 lang=typescript
 *
 * [1626] 无矛盾的最佳球队
 */

// @lc code=start
function bestTeamScore(scores: number[], ages: number[]): number {}
// @lc code=end

解法 1: 排序+动态规划

function bestTeamScore(scores: number[], ages: number[]): number {
  const n = scores.length
  const ids = [...new Array(n).keys()].sort((a, b) => {
    if (ages[a] !== ages[b]) return ages[a] - ages[b]
    return scores[a] - scores[b]
  })

  const dp: number[] = new Array(n).fill(0)
  let res = 0
  for (let i = 0; i < n; i++) {
    const j = ids[i]
    for (let k = 0; k < i; k++) {
      if (scores[ids[k]] <= scores[j]) {
        dp[i] = Math.max(dp[i], dp[k])
      }
    }
    dp[i] += scores[j]
    res = Math.max(res, dp[i])
  }
  return res
}

Case

test.each([
  { input: { scores: [1, 3, 5, 10, 15], ages: [1, 2, 3, 4, 5] }, output: 34 },
  { input: { scores: [4, 5, 6, 5], ages: [2, 1, 2, 1] }, output: 16 },
  { input: { scores: [1, 2, 3, 5], ages: [8, 9, 10, 1] }, output: 6 },
])('input: scores = $input.scores, ages = $input.ages', ({ input: { scores, ages }, output }) => {
  expect(bestTeamScore(scores, ages)).toEqual(output)
})