leetcode1423 Maximum Points You Can Obtain from Cards 解题报告

英文原题

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

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.

分析

    这道题我一开始还想着用动态规划去做，想的太复杂了。其实问题可以归结为左边右边一共选k个数，那么左边选了x个右边就是k-x个，这样只要遍历所有的x就可以得出答案了。

python 代码

class Solution:
    def maxScore(self, cardPoints: List[int], k: int) -> int:
        # left是左边取到第left个
        score = sum(cardPoints[:-k-1:-1])
        tmp = sum(cardPoints[:-k-1:-1])
        for left in range(0, k):
            tmp = tmp + cardPoints[left] - cardPoints[-k+left]
            score = max(score, tmp)
        
        return score