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
This JavaScript solution builds a custom max-heap class to maintain the window of scores efficiently, implementing heap methods for insertion and extraction. This ensures the current maximum score is readily available for each step in the process.