Sponsored
Sponsored
This approach employs dynamic programming in combination with a deque to keep track of the best scores possible when jumping to each index within constraints. By using a decreasing deque, we efficiently maintain the maximum score in a window of size k.
Time Complexity: O(n), because each element is inserted and removed from the deque at most once. Space Complexity: O(k), to store the window of indices in the deque.
1import java.util.Deque;
2import java.util.LinkedList;
3
4class Solution {
5 public int maxResult(int[] nums, int k) {
6 int n = nums.length;
7 Deque<Integer> deque = new LinkedList<>();
8 deque.add(0);
9 for (int i = 1; i < n; i++) {
10 if (deque.getFirst() < i - k) {
11 deque.removeFirst();
12 }
13 nums[i] += nums[deque.getFirst()];
14 while (!deque.isEmpty() && nums[i] >= nums[deque.getLast()]) {
15 deque.removeLast();
16 }
17 deque.addLast(i);
18 }
19 return nums[n - 1];
20 }
21}In Java, a LinkedList is used to implement the deque. The logic of removing indices that are out of bound or non-contributing ensures that only the best possible indices are used for updating the scores at each position in the nums array.
This approach involves using a dynamic programming solution where we keep track of the best scores using a max-heap (priority queue). By pushing elements onto the heap, we ensure that the maximum score is always accessible, facilitating quick updates for each step in our process.
Time Complexity: O(n log k) due to heap operations. Space Complexity: O(k), maintaining up to k elements in the heap.
1#include <queue>
#include <iostream>
class Solution {
public:
int maxResult(std::vector<int>& nums, int k) {
std::priority_queue<std::pair<int, int>> maxHeap;
maxHeap.push({nums[0], 0});
for (int i = 1; i < nums.size(); ++i) {
while (maxHeap.top().second < i - k) {
maxHeap.pop();
}
nums[i] += maxHeap.top().first;
maxHeap.push({nums[i], i});
}
return nums.back();
}
};This C++ solution uses the STL priority_queue to efficiently manage the best possible scores for each range as we move through the nums array, ensuring scores are maximized with optimal heap operations.