LeetCode: Maximum Points You Can Obtain From Cards Solution

Approach

11 2 3 4 5 6 1
2_ _ _
3_ _         _
4_         _ _
5        _ _ _

Implementation

1/**
2 * @param {number[]} cardPoints
3 * @param {number} k
4 * @return {number}
5 */
6// sliding window
7var maxScore = function (cardPoints, k) {
8  const N = cardPoints.length
9  let res = (sum = cardPoints.slice(0, k).reduce((acc, el) => acc + el, 0))
10  for (let i = 1; i < k + 1; i++) {
11    sum += cardPoints[N - i] - cardPoints[k - i]
12    res = Math.max(res, sum)
13  }
14  return res
15}
16
17// memoized recursion (MLE)
18var maxScore = function (cardPoints, k) {
19  const N = cardPoints.length
20  const memo = Array.from({ length: N }, _ => Array(N).fill(undefined))
21
22  const recursion = (i, j, k) => {
23    if (i > N - 1 || j < 0 || k === 0) {
24      return 0
25    }
26    if (memo[i][j] !== undefined) {
27      return memo[i][j]
28    }
29    return (memo[i][j] = Math.max(
30      cardPoints[i] + recursion(i + 1, j, k - 1),
31      cardPoints[j] + recursion(i, j - 1, k - 1)
32    ))
33  }
34
35  return recursion(0, cardPoints.length - 1, k)
36}