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.
1#include <iostream>
2#include <deque>
3#include <vector>
4
5class Solution {
6public:
7 int maxResult(std::vector<int>& nums, int k) {
8 std::deque<int> dq;
9 dq.push_back(0);
10 int n = nums.size();
11 for (int i = 1; i < n; ++i) {
12 while (!dq.empty() && dq.front() < i - k) {
13 dq.pop_front();
14 }
15 nums[i] += nums[dq.front()];
16 while (!dq.empty() && nums[i] >= nums[dq.back()]) {
17 dq.pop_back();
18 }
19 dq.push_back(i);
20 }
21 return nums.back();
22 }
23};This C++ solution uses the STL deque to implement the same sliding window approach. Deque maintains only the indices that give the maximum scores possible for each step taken in the iteration through the 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.