Maximum Points You Can Obtain From Cards

Companies:
  • Google Interview Questions
  • Uber Interview Questions
  • Walmart Labs Interview Questions

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 = [2,5,3,4,5,6,2], k = 3

Output: 13

Example 2:

Input: cardPoints = [4,4,4,4], k = 2

Output: 8

Example 3:

Input: cardPoints = [3,3,4,5,6,3], k = 6

Output: 24

Constraints:
  • 1 <= cardPoints.length <= 10^5
  • 1 <= cardPoints[i] <= 10^4
  • 1 <= k <= cardPoints.length

Solution:

This problem is an example of a sliding window problem. We need to choose cards from both the ends and check which one is greater and keeps on maximize the output. After the iteration, we will be able to find the maximum sum of the card points.

Implementation:

#include <bits/stdc++.h>
#include <iostream>

using namespace std;

int maxScore(vector<int>& cardPoints, int k) {
        int sum = 0, res, len = cardPoints.size();
        
        if (len < k)
            return 0;
        
        for (int i = 0; i < k; ++i)
            sum += cardPoints[i];

        res = sum;
        for (int i = 0; i < k; ++i) {
            sum += cardPoints[len - i - 1] - cardPoints[k - i - 1];
            if (sum > res)
                res = sum;
        }
        
        return res;
    }

int main()
{
    vector<int> arr = {1,2,3,4,5,6,1};
    int k = 3;
    cout<<maxScore(arr,k);
    
}

 

public class Score
{
    static public int maxScore(int[] cardPoints, int k) 
    {
        int res = 0, len = cardPoints.length;
        for (int start = len - k, i = start, win = 0; i < len + k; ++i) 
        {
            win += cardPoints[i % len];
            if (i - start >= k) 
            { 
                win -= cardPoints[(i - k) % len];
            }
            res = Math.max(win, res);
        }
        return res;
    }
    
    public static void main(String[] args) 
    {
        int arr[] = new int[7];
        arr[0] = 1;
        arr[1] = 2;
        arr[2] = 3;
        arr[3] = 4;
        arr[4] = 5;
        arr[5] = 6;
        arr[6] = 1;
        
        int k = 3;
        System.out.println(maxScore(arr,k));
    }
}

 

def maxScore(arr, K):
        N, i, j = len(arr), 0, len(arr) - K
        total = sum(arr[j:])
        best = total
        for _ in range(K):
            total += arr[i] - arr[j]
            best = max(best, total)
            i += 1
            j += 1
        return best
        
arr = [1,2,3,4,5,6,1]
k = 3
print(maxScore(arr,k))

 

Complexity Analysis:

  • Time Complexity: O(K)
  • Space Complexity: O(1)
Scroll to Top