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.
1using System.Collections.Generic;
public class Solution {
public int MaxResult(int[] nums, int k) {
var maxHeap = new PriorityQueue<(int, int), int>(Comparer<int>.Create((a, b) => b - a));
maxHeap.Enqueue((nums[0], 0), nums[0]);
for (int i = 1; i < nums.Length; i++) {
while (maxHeap.Peek().Item2 < i - k) {
maxHeap.Dequeue();
}
nums[i] += maxHeap.Peek().Item1;
maxHeap.Enqueue((nums[i], i), nums[i]);
}
return nums[^1];
}
}Utilizing a priority queue structuring as a max-heap in this C# solution allows for quick access to the maximum score at each stage required when iterating through the nums array.