2023-12-03每日一题

一、题目编号

1423. 可获得的最大点数

二、题目链接

点击跳转到题目位置

三、题目描述

几张卡牌 排成一行，每张卡牌都有一个对应的点数。点数由整数数组 cardPoints 给出。

每次行动，你可以从行的开头或者末尾拿一张卡牌，最终你必须正好拿 k 张卡牌。

你的点数就是你拿到手中的所有卡牌的点数之和。

给你一个整数数组 cardPoints 和整数 k，请你返回可以获得的最大点数。

示例 1：

示例 2：

示例 3：

示例 4：

示例 5：

提示：

• 1 <= cardPoints.length <= 10⁵
• 1 <= cardPoints[i] <= 10⁴
• 1 <= k <= cardPoints.length

四、解题代码

class Solution {
public:
    int maxScore(vector<int>& cardPoints, int k) {
        int sum = 0;
        int n = cardPoints.size();
        int dp[n+5];
        memset(dp, 0, sizeof(dp));
        for(int i = 1; i <= n; ++i){
            dp[i] = dp[i-1] + cardPoints[i-1]; 
            sum += cardPoints[i-1];
        }
        int window_size = n - k;
        int res = 0;
        for(int i = window_size; i <= n; ++i){
            res = max(res, sum - (dp[i] - dp[i - window_size]));
        }
    return res;
    }
};

五、解题思路

(1) 计算出前缀和。

(2) 不管前面和后面取的什么数字，只需要知道取出的数字和为总和减去中间的数字和即可。

(3) 滑动窗口解决该问题。