Recursive brute-force approach to maximum points you can obtain from cards

Question

I came across this question on Leetcode. The question description is as follows:

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.

Return the maximum score you can obtain.

Sample testcases

cardPoints = [1,2,3,4,5,6,1], k = 3 => Output is 12
cardPoints = [2,2,2], k = 2 => Output is 4
cardPoints = [9,7,7,9,7,7,9], k = 7 => Output is 55
cardPoints = [1,1000,1], k = 1 => Output is 1

After looking at the discussion forums, I realized that this could be converted into a sliding window problem where we have to find the smallest subarray sum of length len(cardPoints) - k. While I do understand this, The initial method I tried was brute-force recursive and using dynamic programming to cache intermediate results. Despite this, it still results in a timeout. Is there any other optimization I can make to make my code run faster using this approach?

class Solution {
public:
    int maxScoreUtil(int left, int right,vector<int>& cardPoints, int k,vector<vector<int>>& dp){
        if(k == 0 || left == cardPoints.size() || right < 0)
            return 0;
        
        if(dp[left][right] != -1)
            return dp[left][right];
        
        int val_1 = maxScoreUtil(left+1,right,cardPoints,k-1,dp) + cardPoints[left];
        int val_2 = maxScoreUtil(left,right-1,cardPoints,k-1,dp) + cardPoints[right];
        
        return dp[left][right] = max(val_1,val_2);
    }
    
    int maxScore(vector<int>& cardPoints, int k) {
        int n = cardPoints.size();
        vector<vector<int>> dp(n+1, vector<int>(n+1, -1));
        return maxScoreUtil(0,n-1,cardPoints,k,dp);
    }
};I

Before using DP => 16/40 test cases passed followed by TLE
After using DP => 31/40 test cases passed followed by TLE

Answer 1

You recursive solution takes numbers from [0..left] and [right..n-1] where (left+1)+(n-right) <= k So even if there are k ways to select some elements from left and others from right, i.e. (0,k), (1,k-1), ... (k,0). You look at far more a bigger sample space, in worst case, it would be \$O(n^2)\$. I don't think much can be done with this approach.

Answer 2

RE60K has already critiqued your algorithm, so I'll just leave some minor comments on the code style. These comments won't help you beat the time limit, but they are good habits to get into if you're going to take a coding interview someday, for example.

Your class Solution has only public members. Classes with all public members are frequently defined as structs instead.

In fact, your class has no data members! Classes with no data members should probably just be free functions. See The "OO" Antipattern.

Alternatively, you could keep the class as a sort of "namespace" for these two functions, but mark both functions static, so that you don't waste CPU cycles passing around a this pointer that you'll never use. In this case, you should also mark maxScoreUtil as private because it should never be called by anyone outside the class itself.

Alternatively, notice that your current code is paying for a this pointer and also paying to pass dp as the last argument to maxScoreUtil! It should only ever pay for one or the other. If dp always points to the same vector, maybe dp should be a data member of class Solution.

In all of these cases, the elements of cardPoints are not intended to be modified, so you should mark that parameter as const.

To summarize: Right now your code's skeleton is

class Solution {
public:
    int maxScoreUtil(int left, int right,vector<int>& cardPoints, int k,vector<vector<int>>& dp);
    int maxScore(vector<int>& cardPoints, int k);
};

but it should probably be either

class Solution {
    static int maxScoreImpl(int left, int right, const vector<int>& cardPoints, int k, vector<vector<int>>& dp);
public:
    static int maxScore(const vector<int>& cardPoints, int k);
};

or

static int maxScoreImpl(int left, int right, const vector<int>& cardPoints, int k, vector<vector<int>>& dp);
int maxScore(const vector<int>& cardPoints, int k);

or arguably

class Solution {
    vector<vector<int>> dp;
    vector<int> cardPoints;
    int maxScoreImpl(int left, int right, int k);
public:
    static int maxScore(vector<int> cardPoints, int k) {
       int n = cardPoints.size();
       Solution s{ vector<vector<int>>(n+1, vector<int>(n+1, -1)), std::move(cardPoints) };
       return s.maxScoreImpl(0, n-1, k);
    }
};

---

Notice that I've quietly changed your maxScoreUtil to maxScoreImpl (for "implementation"); that's the usual convention for an internal implementation function. "Util" (for "utilities") is more often used as a namespace or class name for general-purpose utility functions.

---

    if(k == 0 || left == cardPoints.size() || right < 0)
        return 0;

Surely this should say ... || right < left. Also, here and on the next line, you should get in the habit of curly-bracing any time you indent. It'll save you a lot of debugging someday. Consider the difference between

if (failed) {
    puts("oops, exiting");
    exit(0);
}

and

if (failed)
    puts("oops, exiting");
    exit(0);