网页设计网站概述怎么写,1免费网站建站,上海注册公司哪里政策好,查找网站后台入口2023-12-03每日一题
一、题目编号
1423. 可获得的最大点数二、题目链接
点击跳转到题目位置
三、题目描述
几张卡牌 排成一行#xff0c;每张卡牌都有一个对应的点数。点数由整数数组 cardPoints 给出。
每次行动#xff0c;你可以从行的开头或者末尾拿一张卡牌#x…2023-12-03每日一题
一、题目编号
1423. 可获得的最大点数二、题目链接
点击跳转到题目位置
三、题目描述
几张卡牌 排成一行每张卡牌都有一个对应的点数。点数由整数数组 cardPoints 给出。
每次行动你可以从行的开头或者末尾拿一张卡牌最终你必须正好拿 k 张卡牌。
你的点数就是你拿到手中的所有卡牌的点数之和。
给你一个整数数组 cardPoints 和整数 k请你返回可以获得的最大点数。
示例 1
示例 2
示例 3
示例 4
示例 5 提示
1 cardPoints.length 1051 cardPoints[i] 1041 k cardPoints.length
四、解题代码
class Solution {
public:int maxScore(vectorint cardPoints, int k) {int sum 0;int n cardPoints.size();int dp[n5];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) 滑动窗口解决该问题。
