💡 Задача: Лучшая команда, в которой нет конфликтов

Решение:

Интуиция данной задачи:

Эта проблема аналогична проблеме длиннейшей возрастающей подпоследовательности, и мы можем решить ее с помощью динамического программирования.

ПРИМЕЧАНИЕ - ПОЖАЛУЙСТА, СНАЧАЛА ПРОЧИТАЙТЕ ПОДХОД, А ЗАТЕМ ПОСМОТРИТЕ КОД. ПОСЛЕ ОЗНАКОМЛЕНИЯ С ПОДХОДОМ ВЫ ОБЯЗАТЕЛЬНО ПОЙМЕТЕ КОД ПОСТРОЧНО.

Подход к решению данной задачи:

1. Создать парный массив размера n, где n - размер массивов очков и возрастов.
2. В указанный массив записать парные значения очков и возраста каждого игрока.
3. Отсортировать массив пар в порядке возрастания возраста.
4. Инициализируйте массив dp размера n и задайте dp[i] как счет игрока i для всех 0 <= i < n.
5. Инициализируем переменную ans для хранения максимального общего балла.
6. Пройтись циклом по массиву пар от индекса i = 0 до i = n - 1.
7. Для каждого i выполнить цикл по j от 0 до i - 1.
8. Если результат игрока j меньше или равен результату игрока i, обновить dp[i] до максимального значения из dp[i] и dp[j] + score[i].
9. Установите значение ans как максимальное из ans и dp[i].
10. В качестве результата возвращается ans.

Код:

Python

from typing import List
class Solution:
    def bestTeamScore(self, scores: List[int], ages: List[int]) -> int:
        n = len(scores)
        dp = [0] * n
        ans = 0
        players = [(ages[i], scores[i]) for i in range(n)]
        players.sort(key = lambda x: x[0])
        for i in range(n):
            dp[i] = players[i][1]
            for j in range(i):
                if players[j][1] <= players[i][1]:
                    dp[i] = max(dp[i], dp[j] + players[i][1])
            ans = max(ans, dp[i])
        return ans

Временная сложность и пространственная сложность:

Временная сложность: O(n^2)

Пространственная сложность: O(n) // использование дополнительного пространства размера n