1423. Maximum Points You Can Obtain from Cards Medium

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.

In one step, you can take one card from the beginning or from the end of the row. You have to take exactly k cards.

Your score is the sum of the points of the cards you have taken.

Given the integer array cardPoints and the integer k, return the maximum score you can obtain.

Example 1:
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.

Example 2:
Input: cardPoints = [2,2,2], k = 2
Output: 4
Explanation: Regardless of which two cards you take, your score will always be 4.

Example 3:
Input: cardPoints = [9,7,7,9,7,7,9], k = 7
Output: 55
Explanation: You have to take all the cards. Your score is the sum of points of all cards.

Example 4:
Input: cardPoints = [1,1000,1], k = 1
Output: 1
Explanation: You cannot take the card in the middle. Your best score is 1.

Example 5:
Input: cardPoints = [1,79,80,1,1,1,200,1], k = 3
Output: 202

Approach

Input: An integer array cardPoints, and an integer k

Output: Return the maximum score you can obtain by picking k cards from either end

This problem falls under the Fixed-length Sliding Window category.

• Let the array length be n. Since we need to pick k cards from the ends, it's equivalent to leaving exactly a continuous subarray of n - k cards in the middle.
• We can reframe the problem into: find the continuous subarray of length n - k with the minimum sum. The remainder will constitute the cards we've taken. Therefore, the maximum score is simply sum(cardPoints) - minSubarraySum(n - k).

Implementation

python

class Solution:
    def maxScore(self, cardPoints: List[int], k: int) -> int:
        n = len(cardPoints)
        total = sum(cardPoints)  # Calculate total points across all available cards upfront

        # Proceed outright picking everything if parameter 'k' equals array ceiling limits natively capturing top score logically achievable 
        if k == n:
            return total

        # Structuring window proportions leaving middle subsets isolated testing minimal properties representing un-chosen cards
        window_size = n - k

        # Establish starting metric measuring consecutive left-sided subsets bounded by calculated margins exclusively 
        window_sum = sum(cardPoints[:window_size])
        min_subarray_sum = window_sum  # Tracking placeholder evaluating progressive results initialized directly here

        # Displace sliding mechanism gradually rightwards parsing out most diminutive connected fragments possible mapping sequences matching `n-k` limits
        for i in range(window_size, n):
            # Advance values scaling left element outwards updating overall subset totals smoothly evaluating differences appended right
            window_sum += cardPoints[i] - cardPoints[i - window_size]
            # Consistently save minimized outcomes comparatively determining base boundaries recursively overriding older numbers mapping lowest possible combinations recorded exclusively  
            min_subarray_sum = min(min_subarray_sum, window_sum)

        # Result calculation deduces remaining sum omitting lowest middle chunk evaluating maximized bounds 
        return total - min_subarray_sum

javascript

/**
 * @param {number[]} cardPoints
 * @param {number} k
 * @return {number}
 */
var maxScore = function(cardPoints, k) {
    const total = cardPoints.reduce((acc, curr) => acc + curr, 0);

    if (cardPoints.length === k) return total;

    const windowSize = cardPoints.length - k;
    let windowSum = 0;

    for (let i = 0; i < windowSize; i++) {
        windowSum += cardPoints[i];
    }

    let minWindowSum = windowSum;

    for (let j = windowSize; j < cardPoints.length; j++) {
        windowSum += cardPoints[j] - cardPoints[j - windowSize];
        minWindowSum = Math.min(minWindowSum, windowSum);
    }

    return total - minWindowSum;
};

Complexity Analysis

• Time Complexity: O(n)
• Space Complexity: O(1)

Links

1423. Maximum Points You Can Obtain from Cards (English)1423. 可获得的最大点数 (Chinese)