1423. Maximum Points You Can Obtain from Cards

sliding window

T: O(n)
S: O(1)

class Solution {
    public int maxScore(int[] cardPoints, int k) {
        int n = cardPoints.length;
        int total = 0;
        for (int cardPoint : cardPoints) {
            total += cardPoint;
        }
        if (k == n) {
            return total;
        }
        
        int winSize = n - k;
        int res = 0;
        int winSum = 0;
        
        int left = 0;
        for (int right = 0; right < n; right++) {
            winSum += cardPoints[right];
            if (right - left + 1 > winSize) {
                winSum -= cardPoints[left];
                left++;
            }
            if (right - left + 1 == winSize) {
                res = Math.max(res, total - winSum);
            }
        }
        return res;
    }
}

/*
winsize = 1;
0. 1 2
[2,2,2]
2


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.

from start or end


n - k - 1 = 7 - 3 - 1 = 3

0      3 4     => 7 - 3 - 1 = 3
[1,2,3,4,5,6,1]
[__4___]
   [__4___]
     [__4___]  

cal total sum

max(total sum - sliding window sum)

T: O(n)
S: O(1)
*/

new version of sliding window

class Solution {
    public int maxScore(int[] cardPoints, int k) {
        int n = cardPoints.length;
        int w = n - k;
        
        
        int total = 0;
        for (int cardPoint : cardPoints) {
            total += cardPoint;
        }
        if (w == 0) {
            return total;
        }
        
        int sum = 0;
        int left = 0;
        int result = 0;
        for (int right = 0; right < n; right++) {
            sum += cardPoints[right];
            if (right - left + 1 == w) { // 3 - 0 + 1
                result = Math.max(result, total - sum);
                sum -= cardPoints[left];
                left++;
            }
        }
        return result;
    }
}

/*
[1,2,3,4,5,6,1]
         
         
         total - sliding win (len - k)
*/

prefix sum idea

T: O(n)

S: O(1)

class Solution {
    public int maxScore(int[] cardPoints, int k) {
        int n = cardPoints.length;
        int[] presum = new int[n+1];
        presum[0] = 0;
        for (int i = 0; i < cardPoints.length; i++) {
            presum[i+1] = presum[i] + cardPoints[i];
        }
        // sum[i, j] = presum[j+1] - presum[i], 
        // total = presum[n], find max(total - sum[i,j])
        int total = presum[n];
        int winSize = n - k; // size 4
        int res = 0;
        for (int i = 0; i < k+1; i++) { // 0, 1,2,3, win size:4, so move range 7 - 4 = 3
            res = Math.max(res, total - (presum[winSize+i] - presum[i]));
        }
        return res;
    }
}

/*
[1,2,3,4,5,6,1]
[       ]
   [      ]
     [      ]
       [     ]
       
       n - k + i < n+1 (presum len)
       => i < k+1
*/

change to new template style

```java
class Solution {
    public int maxScore(int[] cardPoints, int k) {
        int n = cardPoints.length;
        int w = n - k;
        int total = 0;
        for (int p : cardPoints) {
            total += p;
        }
        if (w == 0) {
            return total;
        }
        // find min sum
        int right = 0;
        int left = 0;
        int result = 0;
        int currentSum = 0;
        while (right < n) {
            int rightNumber = cardPoints[right];
            right++;
            currentSum += rightNumber;
            if (right - left == w) {
                result = Math.max(result, total - currentSum);
                int leftNumber = cardPoints[left];
                left++;
                currentSum -= leftNumber;
            }
        }
        return result;
    }
}
```