LIS
This is a weekly contest problem. The hard part is whether we can realize that this is the longest increasing sequence (LIS) problem. If we realize that this is the longest increasing sequence problem, then it can be solved.
O(n²) LIS
class Solution:
def bestTeamScore(self, scores: List[int], ages: List[int]) -> int:
age_score = [[age, score] for age, score in zip(ages, scores)]
age_score.sort()
dp = [age_score[i][1] for i in range(len(scores))]
for i in range(1, len(ages)):
for j in range(i):
if age_score[i][1] >= age_score[j][1] or age_score[j][0] == age_score[i][0]:
dp[i] = max(dp[i], dp[j] + age_score[i][1])
return max(dp)
