1423.maximum-points-you-can-obtain-from-cards.md

1423. Maximum Points You Can Obtain from Cards

Sliding Window

We can take one card from left and right, but we don't know which side is better. So we can take 0..k cards from left and k..0 cards from right, then we can get the maximum points.

[2,7,8,...,5,1,6], k = 3
 .........,O,O,O    // (0,k)
 O,.........,O,O    // (1,k-1)
 O,O,.........,O    // (2,k-2)
 O,O,O,.........    // (3,k-3)
                    // Find the maximum among them

Why don't we take the maximum card from left or right immediately? (Greedy) Because we're not sure if we can get the maximum points by taking the maximum card from one side. We need to try both sides. See [3, 7, ..., 1, 5], k = 2, if we take 5 first from right, it doesn't lead to the maximum points because we can take [3, 7] from left only.

We take k cards from left or right, then it remains n - k continuous cards. We can calculate the sum of 0..k from left and k..0 from right, then we can get the maximum points by subtracting the sum of the remaining n - k cards from the total sum.

k=3
0 1 2 3 4 5
|---| O O O // sum(3..5) = total - sum(0..2)    
O |---| O O // sum(2..4) = total - sum(0..1)
O O |---| O // sum(1..5) = total - sum(0..0)
O O O |---| // sum(0..4) = total - sum(1..5)

Then this is a fixed size sliding window problem:

• Window: The sum of subarray size n - k.

Or it finds the minimum of n - k sliding window.

fun maxScore(cardPoints: IntArray, k: Int): Int {
    val n = cardPoints.size
    var totalSum = 0
    for (p in cardPoints) {
        totalSum += p
    }
    var sum = 0
    var maxScore = 0
    val windowSize = n - k
    for (i in cardPoints.indices) {
        sum += cardPoints[i]
        if (i >= windowSize) {
            sum -= cardPoints[i - windowSize]
        }
        if (i >= windowSize - 1) {
            maxScore = maxOf(maxScore, totalSum - sum)
        }
    }
    return maxScore
}

• Time Complexity: O(n)
• Space Complexity: O(1)

Sliding Window (Optimized)

We take all left first, and start to take one from right, and remove one from left. We can iterate from 0..k and calculate the sum of 0..i from left and n - i..n from right, then we can get the maximum points. (Reversed direction of the previous solution)

O,O,O,.........    // (k,0)
O,O,.........,O    // (k-1,1)
O,.........,O,O    // (k-2,2)
.........,O,O,O    // (k-3,3)
                   // Find the maximum among them

The detail steps are as follows:

// We can sum the first `k` cards from left at the beginning
O O O, ..., X X X
|-k-|

// Then we can iterate to remove the card from left and add the card from right
O O X, ..., X X O
    -           +
    // Remove nums[k - left], add nums[n - left]
O X X, ..., X O O
X X X, ..., O O O

為何是 k - left 或者 n - left? 可以這麼想，我現在有一個長度 n 的陣列，我要依序移除最後一個元素，那麼就會 for (i = 1..n) remove(nums[n - i])。也就是遍歷長度，移除 n - i 的元素。k - left 是左半邊長度為 n == k 的部分，k - left 就相當於等價 n - i where n = k, i = left 的意思。

[O, O, O, ...]
 |--k--|
       i

fun maxScore(cardPoints: IntArray, k: Int): Int {
    val n = cardPoints.size
    var sum = 0
    for (i in 0 until k) {
        sum += cardPoints[i]
    }
    var ans = sum // Take the first `k` cards from left: [O,O,O,....]

    // Start to iterate to remove the card from left and add the card from right
    /**
    O O O, .... var ans = sum
    O O, ..., O
    O, ..., O O
    ...., O O O
     */
    for (left in 1..k) {
        // Add the right
        sum += cardPoints[n - left]
        // Remove the left card from the "right" side in the left part
        // 0 1 2
        // O O X Remove nums[k - left] = nums[3 - 1] = nums[2]
        // O X X Remove nums[3 - 2] = nums[1]
        // X X X Remove nums[3 - 3] = nums[0]
        sum -= cardPoints[k - left]
        ans = maxOf(ans, sum)
    }
    return ans
}

• Time Complexity: O(k)
• Space Complexity: O(1)