Сложность: medium
Есть несколько карт, расположенных в ряд, и у каждой карты есть определенное количество очков. Очки представлены в виде целочисленного массива cardPoints.
За один шаг вы можете взять одну карту либо с начала, либо с конца ряда. Вы должны взять ровно k карт.
Ваш результат - это сумма очков взятых карт.
Дан целочисленный массив cardPoints и целое число k, верните максимальное количество очков, которое вы можете получить.
Пример:
Input: cardPoints = [1,2,3,4,5,6,1], k = 3
Output: 12
Explanation: After the first step, your score will always be 1. However, choosing the rightmost card first will maximize your total score. The optimal strategy is to take the three cards on the right, giving a final score of 1 + 6 + 5 = 12.
👨💻 Алгоритм:
1⃣Инициализируйте два массива размера k + 1, frontSetOfCards и rearSetOfCards, чтобы хранить суммы очков, полученных при выборе первых i карт и последних i карт в массиве.
2⃣Рассчитайте префиксные суммы для первых k карт и последних k карт.
3⃣Итерируйте от 0 до k и вычисляйте возможное количество очков, выбирая i карт с начала массива и k - i карт с конца, обновляя максимальный результат при необходимости.
😎 Решение:
class Solution:
def maxScore(self, cardPoints: List[int], k: int) -> int:
n = len(cardPoints)
frontSetOfCards = [0] * (k + 1)
rearSetOfCards = [0] * (k + 1)
for i in range(k):
frontSetOfCards[i + 1] = cardPoints[i] + frontSetOfCards[i]
rearSetOfCards[i + 1] = cardPoints[n - i - 1] + rearSetOfCards[i]
maxScore = 0
for i in range(k + 1):
currentScore = frontSetOfCards[i] + rearSetOfCards[k - i]
maxScore = max(maxScore, currentScore)
return maxScore
Ставь 👍 и забирай 📚 Базу знаний