如何搭建一个视频网站,网络营销包括哪些策略,公司管理,做公司网站视频文章目录 题目思路代码结果 题目
题目链接 给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。
一开始你在下标 0 处。每一步#xff0c;你最多可以往前跳 k 步#xff0c;但你不能跳出数组的边界。也就是说#xff0c;你可以从下标 i 跳到 [i 1#xff0c; min(n -… 文章目录 题目思路代码结果 题目
题目链接 给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。
一开始你在下标 0 处。每一步你最多可以往前跳 k 步但你不能跳出数组的边界。也就是说你可以从下标 i 跳到 [i 1 min(n - 1, i k)] 包含 两个端点的任意位置。
你的目标是到达数组最后一个位置下标为 n - 1 你的 得分 为经过的所有数字之和。
请你返回你能得到的 最大得分 。 示例 1 输入nums [1,-1,-2,4,-7,3], k 2 输出7 解释你可以选择子序列 [1,-1,4,3] 上面加粗的数字和为 7 。 示例 2 输入nums [10,-5,-2,4,0,3], k 3 输出17 解释你可以选择子序列 [10,4,3] 上面加粗数字和为 17 。 示例 3 输入nums [1,-5,-20,4,-1,3,-6,-3], k 2 输出0 提示 1 nums.length, k 105104 nums[i] 104 思路
设 dp[i] 为“从索引 i 开始到达终点的最大分数”。dp[i] 的答案是 nums[i] max{dp[ij]} for 1 j k。这给出了一个 On*k 解。 代码如下
class Solution {
public:int maxResult(vectorint nums, int k) {int dp[(int)1e510]{};int nnums.size();if(n0)return 0;for(int i0;in;i)dp[i]INT_MIN;dp[0]nums[0];if(kn)kn;for(int i1;ik;i){for(int j0;ji;j){dp[i]max(dp[j]nums[i],dp[i]);}}for(int ik;in;i){for(int ji-k;ji;j){dp[i]max(dp[j]nums[i],dp[i]);}}return dp[n-1];}
};但是这样就会超时间与其遍历每一个 i 都要找前面 k 个中的最大值不如跟踪堆中最大的 dp[i] 值并从右到左计算 dp[i]。当堆中的最大值超出当前索引的范围时将其删除并继续检查。
代码
class Solution {
public:int maxResult(vectorint nums, int k) {int n nums.size();vectorintdp(n,INT_MIN);priority_queuepairint,intq;for(int i 0; i n; i){while(q.size() i - q.top().second k){q.pop();}if(q.empty()){dp[i] nums[i];q.push({nums[i],i});}else{dp[i] nums[i] q.top().first;q.push({dp[i], i});}}return dp[n - 1];}
};结果
