题目描述：
给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。
一开始你在下标 0 处。每一步，你最多可以往前跳 k 步，但你不能跳出数组的边界。也就是说，你可以从下标 i 跳到 [i + 1， min(n - 1, i + k)] 包含 两个端点的任意位置。
你的目标是到达数组最后一个位置（下标为 n - 1 ），你的 得分 为经过的所有数字之和。
请你返回你能得到的 最大得分 。
数据范围：
$1\le nums.len, k \le 10^5, -10^4 \le nums[i] \le 10^4$
题解：
假设 $dp[i]$ 为从 $0$ 跳到 $i$ 的最大得分，或者 $dp[i]$ 为从 $0$ 跳到 $nums[n - 1]$ 的最大得分。这里使用后者，然后可以得到
但是这样的话复杂度比较高是 $n \times k$ 的，过不了。
可以考虑优化取 $max$ 操作，维护后面长度为 $k$ 的最大值。滑动窗口最大值，可以使用单调队列维护，因为这个是倒着遍历的，所以可以使用一个单调减队列，队首就是最大值。
每次首先检查队列是否超过了 $k$ ，然后取出队首，更新 $dp[i]$ ，最后维护单调性，弹出队尾元素，直到队尾元素大于当前 $dp[i]$ 。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| auto optimize_cpp_stdio = []()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
return 0;
}();
class Solution
{
public:
const static int maxn = 1e5 + 10;
const static int maxm = 1e5 + 10;
const static long long mod = 1e9 + 7;
const long long INF_LL = 0x3f3f3f3f3f3f3f3f;
const int INF = 0x3f3f3f3f;
int maxResult(vector<int> &nums, int k)
{
int n = nums.size();
vector<int> dp(n, -INF);
dp[n - 1] = nums[n - 1];
for (int i = n - 2; i >= 0; --i)
{
for (int j = i + 1; j <= min(i + k, n - 1); ++j)
{
dp[i] = max(dp[i], nums[i] + dp[j]);
}
}
return dp[0];
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
| auto optimize_cpp_stdio = []()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
return 0;
}();
class Solution
{
public:
const static int maxn = 1e5 + 10;
const static int maxm = 1e5 + 10;
const static long long mod = 1e9 + 7;
const long long INF_LL = 0x3f3f3f3f3f3f3f3f;
const int INF = 0x3f3f3f3f;
int maxResult(vector<int> &nums, int k)
{
int n = nums.size();
vector<int> dp(n, -INF);
dp[n - 1] = nums[n - 1];
vector<int> q(n);
int hh = 0, tt = -1;
q[++tt] = n - 1;
for (int i = n - 2; i >= 0; --i)
{
while (tt >= hh && q[hh] - i > k)
++hh;
dp[i] = nums[i] + dp[q[hh]];
while (tt >= hh && dp[i] > dp[q[tt]])
--tt;
q[++tt] = i;
}
return dp[0];
}
};
|