题目描述
给你一个下标从 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 <= 105
-104 <= nums[i] <= 104
算法1
dp 动态规划算法
dp[i] = max(dp[i-1]~~ dp[i-k])+ nums[i];
然而TLE了
10^9的时间复杂度
考虑到max(dp[i-1]~~ dp[i-k]) 可以使用单调队列优化
时间复杂度就是O(n)
C++ 代码
class Solution {
public:
int maxResult(vector<int>& nums, int k) {
deque<pair<int, int>> deq;
deq.push_back({ nums[0],0 });
int ans = nums[0];
//int ans= 0;
for (int i = 1; i < nums.size(); i++) {
while (!deq.empty()) {
if (i - deq.front().second > k) {
deq.pop_front();
}
else {
break;
}
}
//当前索引的数组数值 加载那个DP上
//由于上面的代码 进入队列的dp值肯定与当前索引i 相差k以内
ans = nums[i] + deq.front().first;
//这里是优化dp值 由于当前队列里的dp元素都是从i-k之前的最佳dp转移过来的
//那么当前索引下的数值较大 就不必考虑那些数组里索引数值较小的dp了
while (!deq.empty()) {
if (ans > deq.back().first) {
deq.pop_back();
}
else {
break;
}
}
//计算得出的当前索引的dp最优值 入队列
deq.push_back({ ans,i });
}
return ans;
}
};