1626.Best Team With No Conflicts
===

###### tags: `Medium`,`Array`,`DP`,`Sorting`

[1626. Best Team With No Conflicts](https://leetcode.com/problems/best-team-with-no-conflicts/)

### 題目描述

You are the manager of a basketball team. For the upcoming tournament, you want to choose the team with the highest overall score. The score of the team is the **sum** of scores of all the players in the team.

However, the basketball team is not allowed to have **conflicts**. A **conflict** exists if a younger player has a **strictly higher** score than an older player. A conflict does **not** occur between players of the same age.

Given two lists, `scores` and `ages`, where each `scores[i]` and `ages[i]` represents the score and age of the i^th^ player, respectively, return *the highest overall score of all possible basketball teams.*

### 範例

**Example 1:**

Input: scores = [1,3,5,10,15], ages = [1,2,3,4,5]
Output: 34
Explanation: You can choose all the players.

**Example 2:**

Input: scores = [4,5,6,5], ages = [2,1,2,1]
Output: 16
Explanation: It is best to choose the last 3 players. Notice that you are allowed to choose multiple people of the same age.

**Example 3:**

Input: scores = [1,2,3,5], ages = [8,9,10,1]
Output: 6
Explanation: It is best to choose the first 3 players. 

**Constraints**:

* 1 <= `scores.length`, `ages.length` <= 1000
* `scores.length` == `ages.length`
* 1 <= `scores[i]` <= 10^6^
* 1 <= `ages[i]` <= 1000

### 解答
#### Python

class Solution:
    def bestTeamScore(self, scores: List[int], ages: List[int]) -> int:

        
        Q = sorted( zip(ages,scores), key = lambda x: x[0]*10000000+x[1])
        dp = [ (0, 0)] # (max_score, total_score)
        #print(Q)
        for age, sc in Q:
            cur_max_score = -1
            for max_score, total_score in dp:
                if sc >= max_score:
                    if total_score + sc > cur_max_score:
                        cur_max_score = total_score + sc
                else:
                    break            


            dp.append( (sc, cur_max_score) )
            dp = sorted(dp, key=lambda x: x[0]*1000000 + x[1] )
            #print(dp)

        return max( [ x[1] for x in dp])

思路:
dp題，首先把球員按照 年紀，同年紀按照得分能力 由低到高排序

DP陣列存的是(max_score,max_total)。
其意義是在已看過的球員中，若得分能力最高為max_score, 則最大總分為max_total

接著由年紀小球員的開始看，對每個球員檢查他的分數是否小於 dp中每個項目的max_score，若是則考慮更新dp陣列。
維護DP陣列 直到看過所有球員

> [name=玉山]

### Reference

[回到題目列表](https://hackmd.io/@Marsgoat/leetcode_every_day)