LeetCode "Maximum Points You Can Obtain from Cards" python 代码不工作，我需要告诉我为什么

Question

我无法理解我的代码在 LeetCode 问题“您可以从卡片中获得的最大分数”中遇到的问题

首先，我将post这里的问题：

有几张牌排成一排，每张牌都有相应的点数，点数在整数数组cardPoints中给出。

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

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

给定整数数组cardPoints和整数k，return你可以获得的最高分数。

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

这里是 link leetcode 上的问题：

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

如果您熟悉这个问题，您可能会明白解决这个问题的最佳方法是使用滑动 window。

我明白了，并且能够让一个版本正常工作。但我的第一次尝试是暴力解决这个问题，检查列表中的第一项和最后一项，取最大值，然后将其从列表中弹出。

这是我使用的代码：

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

这个问题我已经一步步走过来了，我不明白为什么会期待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 上的解决方案，它被接受了。

LeetCode "Maximum Points You Can Obtain from Cards" python 代码不工作，我需要告诉我为什么

LeetCode "Maximum Points You Can Obtain from Cards" python code not working and I need to be shown why

python

algorithm

dynamic-programming