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

user_12711820 0
Viewed 503

I am having an issue understanding the problem that my code is having with the LeetCode question, "Maximum Points You Can Obtain from Cards"

First, I will post the question here:

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

Constraints:

1 <= cardPoints.length <= 10^5

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

1 <= k <= cardPoints.length

Here is a link to the question on leetcode:

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

If you are familiar with the question, you will probably understand that the best way to approach this would be with a sliding window.

I understand that, and was able to get a version working. But my first attempt was to brute force through this, checking the first and last item in the list, taking the max, and then popping it out of the list.

Here is the code I was using:

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)

As you can see, this is a very messy approach, but it isn't working. It works on a few of the test cases, but the one that it stops on is here:

Input:

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

Output:

207

Expected:

232

I have walked through this problem step by step, and I don't understand why it would be expecting 232.

As I understand it, we should be taking the first or last item from the list, based on which value is higher.

In this case, we would first compare 11 and 72.

Taking 72 into the new list, we then compare 11 and 29.

Taking 29 into the new list, we then compare 11 and 86.

Taking 86 into the new list, we then compare 11 and 20.

Taking 20 into the new list, we get a final list of 72, 29, 86, 20.

Totaling that up, 72 + 29 + 86 + 20 = 207, which is the answer that my code got.

Why was the code expecting 232?

Can someone please explain what I am missing here?

dynamic-programming algorithm python
1 Answers

As already noted in the comments, you shouldn't use a greedy approach for this because you may choose the wrong sequence otherwise. For example, if your array is [1,100,3,2] and k=2, then your algorithm yields 5, although it has to be 101.

The right approach is to try every array subsegment of length k between cardPoints[-k] and cardPoints[k - 1] (both inclusive), and pick the one with the maximum sum. You will need to check only k + 1 segments, and the time complexity will only be O(k) (see below).

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

We start with sum of the left segment, and then gradually convert it into the right segment. On each step, we make sure that the max score is updated.

I ran the solution on LeetCode and it got accepted just fine.

user_10553950
Related