learning/l33tcode/maximum-points-you-can-obtain-from-cards.py at master · fspv/learning · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
from functools import lru_cache


class Solution:
    def maxScore(self, card_points: List[int], cards: int) -> int:
        total = sum(card_points)

        if cards == len(card_points):
            return total

        range_sum = 0
        min_range_sum = total

        for pos in range(len(card_points)):
            if pos >= (len(card_points) - cards):
                min_range_sum = min(min_range_sum, range_sum)
                range_sum -= card_points[pos - (len(card_points) - cards)]

            range_sum += card_points[pos]

        min_range_sum = min(min_range_sum, range_sum)

        return total - min_range_sum

    def maxScoreBruteForce(self, card_points: List[int], cards: int) -> int:
        @lru_cache(None)
        def dp(start: int, end: int, cards: int) -> int:
            if cards == 0:
                return 0

            if start > end:
                return 0

            return max(
                dp(start + 1, end, cards - 1) + card_points[start],
                dp(start, end - 1, cards - 1) + card_points[end],
            )

        return dp(0, len(card_points) - 1, cards)