Maximum Points You Can Obtain From Cards - Leetcode Solution

Maximum Points You Can Obtain From Cards is a problem on LeetCode that asks you to find the maximum number of points that you can obtain from selecting a given number of cards from an array of cards, with the constraint that you can only select from the beginning or end of the array.

To solve this problem, we can use dynamic programming. We can create two arrays, left and right, where left[i] represents the maximum points that can be obtained from selecting i cards from the beginning of the array, and right[i] represents the maximum points that can be obtained from selecting i cards from the end of the array.

First, we can fill the left array by taking the first card and adding it to the sum of the maximum points that can be obtained from selecting i-1 cards from the beginning of the array. We can use a for loop to iterate through the array from 1 to k, where k is the number of cards we want to select.

Next, we can fill the right array in a similar manner, by taking the last card and adding it to the sum of the maximum points that can be obtained from selecting i-1 cards from the end of the array. We can use a for loop to iterate through the array from n-1 to n-k-1, where n is the length of the array and k is the number of cards we want to select.

Finally, we can iterate through the left and right arrays to find the maximum sum of points that can be obtained by selecting cards from both sides of the array. We can use a for loop to iterate through the array from 0 to k, where k is the number of cards we want to select, and add the maximum points from selecting i cards from the left array and k-i cards from the right array.

Here's the Python code:

def maxScore(cardPoints: List[int], k: int) -> int:
    n = len(cardPoints)
    left = [0] * (k+1)
    right = [0] * (k+1)
    
    for i in range(1, k+1):
        left[i] = left[i-1] + cardPoints[i-1]
        
    for i in range(n-1, n-k-1, -1):
        right[n-i] = right[n-i-1] + cardPoints[i]
        
    max_score = 0
    for i in range(k+1):
        max_score = max(max_score, left[i] + right[k-i])
        
    return max_score

The time complexity of this solution is O(k), since we iterate through the array twice and then iterate through the left and right arrays once. The space complexity is O(k), since we use two arrays of size k+1.

1