1423. Maximum Points You Can Obtain from Cards

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.

Example 1:

Input: cardPoints = [1,2,3,4,5,6,1], k = 3
Output: 12
Explanation: After the first step, your score will always be 1. However, choosing the rightmost card first will maximize your total score. The optimal strategy is to take the three cards on the right, giving a final score of 1 + 6 + 5 = 12.

Example 2:

Input: cardPoints = [2,2,2], k = 2
Output: 4
Explanation: Regardless of which two cards you take, your score will always be 4.

Example 3:

Input: cardPoints = [9,7,7,9,7,7,9], k = 7
Output: 55
Explanation: You have to take all the cards. Your score is the sum of points of all cards.

Example 4:

Input: cardPoints = [1,1000,1], k = 1
Output: 1
Explanation: You cannot take the card in the middle. Your best score is 1. 

Example 5:

Input: cardPoints = [1,79,80,1,1,1,200,1], k = 3
Output: 202

Constraints:

• 1 <= cardPoints.length <= 10^5
• 1 <= cardPoints[i] <= 10^4
• 1 <= k <= cardPoints.length

---

给定一个数组，要从中选k个数，每次只能从左边选或从右边选，问选出的数的和最大是多少。

转换思路，无论从左边选多少个，从右边选多少个，剩余的数都是中间区域的某一段数。要使选出来的数和最大，则相当于要使剩下的连续区间的数和最小。所以可以设置一个大小为n-k的滑动窗口，求该滑动窗口的最小和，则用总和减去该最小和即为最终结果。

完整代码如下：

class Solution {
public:
	int maxScore(vector<int>& cardPoints, int k) {
		int sum = 0, n = cardPoints.size();
		for (int i = 0; i < n; ++i)sum += cardPoints[i];
		if (k == n)return sum;

		int min_window_sum = 0, i = 0, j = n - k - 1;
		for (int k = i; k <= j; ++k)min_window_sum += cardPoints[k];
		int cur_window_sum = min_window_sum;
		while (j < n) {
			if (j == n - 1)break;
			cur_window_sum = cur_window_sum + cardPoints[++j] - cardPoints[i++];
			min_window_sum = min(min_window_sum, cur_window_sum);
		}
		return sum - min_window_sum;
	}
};

本代码提交AC，用时152MS。

我之前的想法一直是正向思维，即模拟每次拿左边或右边，甚至还用DP来求解，但都无果。

看讨论区后还是很有启发，无论你当前这一步是拿左边还是右边，经过k轮之后的最终效果是，左边拿了连续的a的，右边拿了连续的k-a个。所以只需要对最终左边拿了几个进行DP建模，而无需模拟每一步是拿了左边还是右边。DP方法可看讨论区： https://leetcode.com/problems/maximum-points-you-can-obtain-from-cards/discuss/598111/Java-dp-solution(explanation-with-picture) 。