问题描述
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
问题分析
1.dp方式求解
由于每次只能从数组开头或者末尾取一张卡片，那么如果对于取完一张卡片后剩余的数组，其最优解已知，那么就有
f(cardPoints[0..n], k) = max(f(cardPoints[1..n], k-1)+cardPoints[0], f(cardPoints[0..n-1], k-1)+cardPoints[n])
即当前数组下的最优解等于取开头或者末尾元素之后，加上子问题的最优解
2.滑动窗口方式求解
由于最终抽到的卡片数固定为k，那么我们可以将原数组的开头和末尾看做是“相连”的，从全部取开头卡片这种方式为初始case，不断向后滑动1个元素，直至变为全部取末尾的元素这种case；在这个过程中，记录最大值即为所求
示例代码
// 滑动窗口方式求解
func maxScore(cardPoints []int, k int) int {
maxsum, sum := 0, 0
// 全部取开头元素，作为base case
for i := 0; i < k; i++ {
sum += cardPoints[i]
}
maxsum = sum
length := len(cardPoints)
for i := k - 1; i >= 0; i-- {
// 不断向末尾滑动一个元素；更新sum对应的值
sum = sum - cardPoints[i] + cardPoints[length-k+i]
if sum > maxsum {
maxsum = sum
}
}
return maxsum
}
// dp方式求解
func maxScore(cardPoints []int, k int) int {
if k <= 0 {
return 0
}
// base case
if k == 1 {
return max(cardPoints[0], cardPoints[len(cardPoints)-1])
}
// 要么取开头的元素，要么取末尾元素；两者取子问题的较大值
return max(cardPoints[0]+maxScore(cardPoints[1:], k-1), cardPoints[len(cardPoints)-1]+maxScore(cardPoints[:len(cardPoints)-1], k-1))
}
func max(a int, b int) int {
if a > b {
return a
}
return b
}