1423. Maximum Points You Can Obtain from Cards

Question

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.

Solution 1

这种取两端的问题可以转化为取中间连续k个元素之和最小。

计算所有数字的和sum。
然后用维护一个宽度为k的窗口内的加和temp，并记录其最小值min。

返回sum - min，结果即是取两侧时可以取的最大值。

Code

class Solution {
    public int maxScore(int[] cardPoints, int k) {
        int n = cardPoints.length, sum = 0;
        for(int point : cardPoints) sum += point; //求所有数值的和
        if(k == n) return sum;
        int left = 0, right = n-k, temp = 0, min = 0;
        
        for(int i = 0; i < n-k; i++){
            temp += cardPoints[i];
            min = temp;
        }
        while(right < n){   //维护窗口内的temp，并更新min
            temp += cardPoints[right] - cardPoints[left];; 
            min = Math.min(min, temp);
            right++;
            left++;
        }
        return sum - min;
    }
}

Solution 2

分别计算从两侧开始的加和并记录在两个数组left[]和right[]上。

然后分别取两个指针，左侧指针l从0开始遍历到k，右侧指针对应的位置为l+n-k。计算并更新最大值max。

Code

class Solution {
    public int maxScore(int[] cardPoints, int k) {
        int n = cardPoints.length, max = 0;
        int[] left = new int[n+1], right = new int[n+1];
        
        for(int i = 0; i < n; i++){
            left[i+1] = left[i] + cardPoints[i];
            right[n-i-1] = right[n-i] + cardPoints[n-i-1];
        }
        
        for(int l = 0; l <= k; l++){
            max = Math.max(max, left[l] + right[n-k+l]);
        }
        
        return max;
    }
}