LeetCode“您可以从卡中获得的最大点数”python代码不起作用，我需要说明原因

Question

我在理解我的代码在LeetCode问题“您可以从卡中获得的最大积分”时遇到了问题

首先，我将在这里发布问题：

---

有几张卡片排成一行，每张卡片都有一个相关的点数。点数在整数数组cardPoints中给出

在一个步骤中，您可以从行首或行尾取出一张卡。你必须拿k牌

你的分数是你所拿牌的点数之和

给定整数数组cardPoints和整数k，返回可以获得的最大分数

示例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.

例2：

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

例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.

例4：

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

例5：

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

限制条件：

1 <= cardPoints.length <= 10^5

1 <= cardPoints[i] <= 10^4

1 <= k <= cardPoints.length

---

以下是有关leetcode的问题的链接：

https://leetcode.com/problems/maximum-points-you-can-obtain-from-cards

如果你熟悉这个问题，你可能会明白最好的方法是使用滑动窗口

我理解这一点，并且能够让一个版本正常工作。但我的第一次尝试是强行通过这个，检查列表中的第一项和最后一项，取最大值，然后将其从列表中弹出

以下是我使用的代码：

class Solution:
    def maxScore(self, cardPoints: List[int], k: int) -> int:
        myList = []
        if len(cardPoints) == k:
            return sum(cardPoints)
        else:
            while len(myList) < k:
                if cardPoints[0] > cardPoints[-1]:
                    myList.append(cardPoints[0])
                    cardPoints.pop(0)
                elif cardPoints[0] < cardPoints[-1]:
                    myList.append(cardPoints[-1])
                    cardPoints.pop(-1)
                elif cardPoints[0] == cardPoints[-1]:
                    if cardPoints[1] > cardPoints[-2]:
                        myList.append(cardPoints[0])
                        cardPoints.pop(0)
                    elif cardPoints[1] < cardPoints[-2]:
                        myList.append(cardPoints[-1])
                        cardPoints.pop(-1)
                    else: 
                        myList.append(cardPoints[-1])
                        cardPoints.pop(-1)
            return sum(myList)

正如您所看到的，这是一个非常混乱的方法，但它不起作用。它可以在一些测试用例上工作，但它停止的测试用例如下：

Input:

[11,49,100,20,86,29,72]
4

Output:

207

Expected:

232

我已经一步一步地解决了这个问题，但我不明白为什么会这样

据我所知，我们应该从列表中选择第一项或最后一项，根据哪个值更高

在本例中，我们将首先比较11和72

将72放入新列表，然后比较11和29

将29放入新列表，然后比较11和86

将86放入新列表，然后比较11和20

将20放入新列表中，我们得到72, 29, 86, 20的最终列表

加起来，72 + 29 + 86 + 20 = 207，这是我的代码得到的答案

为什么代码需要232

有人能解释一下我遗漏了什么吗

Answer 1

正如在评论中已经提到的，你不应该使用贪婪的方法，因为否则你可能会选择错误的序列。例如，如果您的数组是[1,100,3,2]和k=2，那么您的算法将产生5，尽管它必须是101

正确的方法是尝试cardPoints[-k]和cardPoints[k - 1]之间长度为k的每个数组子段（两者都包括在内），然后选择一个和最大的数组子段。您只需要检查k + 1段，时间复杂度仅为O（k）（见下文）

def maxScore(self, cardPoints: List[int], k: int) -> int:
    currentScore = sum(cardPoints[:k])
    maxScore = currentScore
    size = len(cardPoints)
    for i in range(k):
        currentScore += cardPoints[size - 1 - i]
        currentScore -= cardPoints[k - 1 - i]
        maxScore = max(maxScore, currentScore)
        
    return maxScore 

我们从左段的和开始，然后逐渐将其转换为右段。在每一步中，我们都要确保更新最大分数

我在LeetCode上运行了解决方案，它被很好地接受了