Maximum Points You Can Obtain from Cards — LeetCode 1423 Python Solution

The problem

There are several cards arranged in a row, and each card has an associated number of points. The points are given in the integer array cardPoints.

Example

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.

Python solution

class Solution:
    def maxScore(self, cardPoints: List[int], k: int) -> int:
        ans = s = sum(cardPoints[-k:])
        for i, x in enumerate(cardPoints[:k]):
            s += x - cardPoints[-k + i]
            ans = max(ans, s)
        return ans

Complexity

Pattern: Sliding Window

Collapse a nested loop over every subarray into a single pass with two indices. LeetCode 1423. Maximum Points You Can Obtain from Cards is filed here because LeetCode tags it Sliding Window, which is the vocabulary this hub collects.

The sliding window guide has the Python template for the pattern and the 116 LeetCode problems that use it.

Related problems