Leetcode 1696: Jump Game VI
You are given a 0-indexed integer array ’nums’ and an integer ‘k’. You start at index 0 and can jump up to ‘k’ steps forward at a time. Your task is to find the maximum sum of elements you can get by jumping to the last index, visiting subarrays of unique elements.
Problem
Approach
Steps
Complexity
Input: The input consists of an array 'nums' containing integers and an integer 'k' which defines the maximum jump range.
Example: [3, -2, 5, -1, 2, 4], k = 2
Constraints:
• 1 <= nums.length, k <= 10^5
• -10^4 <= nums[i] <= 10^4
Output: The output is a single integer representing the maximum score you can obtain by jumping to the last index.
Example: 9
Constraints:
• The score is the sum of the elements in the subsequence of jumps you choose.
Goal: The goal is to compute the maximum score from jumping to the last index while maintaining the sum of visited elements.
Steps:
• Start from the first index (0) and maintain a deque to track the indices of the array.
• At each index, compute the best score by considering jumps from the previous valid indices (within the range of 'k' jumps).
• For each step, update the current score based on the previous best score.
• Ensure that the deque only holds indices that provide the highest score within the jump range.
Goal: The input array is always non-empty and contains positive integers.
Steps:
• The array length and k are both between 1 and 10^5.
• The elements in the array are integers between -10^4 and 10^4.
Assumptions:
• You will always have a valid input, i.e., the array will not be empty.
• Input: [3, -2, 5, -1, 2, 4], k = 2
• Explanation: The maximum score is achieved by jumping through the subsequence [3, -2, 5, 2, 4], which results in a sum of 9.
• Input: [1, -3, 2, 4, -1, 2], k = 3
• Explanation: The best subsequence to jump through is [1, -3, 2, 4, 2], resulting in a sum of 7.
Approach: To solve this problem efficiently, use dynamic programming with a deque to maintain the optimal subsequence sums for valid jumps.
Observations:
• The sliding window approach is helpful here, as we need to consider the best jump within the range of 'k'.
• We can use a deque to keep track of the maximum score in the sliding window of size 'k'.
Steps:
• Start by initializing a deque to store indices, and set the first element of 'nums' as the starting point.
• Iterate through the array, updating the score for each index based on the maximum score from valid previous indices.
• Remove indices from the deque that are outside the current valid jump range.
• At each step, update the score by adding the current element to the maximum score from previous valid indices.
Empty Inputs:
• There are no empty inputs since the array will have at least one element.
Large Inputs:
• For large inputs, ensure the solution handles arrays with lengths up to 10^5 efficiently.
Special Values:
• When the array contains all negative numbers, the result will be the maximum negative number within the valid subsequence.
Constraints:
• Ensure that the time complexity remains O(n) to handle large input sizes.
int maxResult(vector<int>& nums, int k) {
int n = nums.size();
deque<int> dq = {0};
for(int i = 1; i < n; i++) {
nums[i] = nums[dq.front()] + nums[i];
while(!dq.empty() && nums[dq.back()] <= nums[i])
dq.pop_back();
dq.push_back(i);
if(i - dq.front() >= k) dq.pop_front();
}
return nums[n - 1];
}
1 : Function Definition
int maxResult(vector<int>& nums, int k) {
Defines the function `maxResult` that takes a vector `nums` and an integer `k`, returning the maximum result achievable by making jumps in the array with a maximum jump length of `k`.
2 : Variable Initialization
int n = nums.size();
Initialize `n` to store the size of the `nums` array, which helps in managing the loop boundaries.
3 : Deque Initialization
deque<int> dq = {0};
Initialize a deque `dq` with the index `0` to represent the first element of the array, as it is the starting point for the score calculations.
4 : Main Loop
for(int i = 1; i < n; i++) {
The main loop that iterates through the array starting from the second element (`i = 1`) to the last element.
5 : Score Update
nums[i] = nums[dq.front()] + nums[i];
Update `nums[i]` to be the sum of the current value `nums[i]` and the value at the front of the deque (`dq.front()`), which holds the maximum value within the current window.
6 : Deque Maintenance
while(!dq.empty() && nums[dq.back()] <= nums[i])
Ensure that the deque maintains the largest value at the front by removing indices of values that are less than or equal to `nums[i]`.
7 : Deque Maintenance
dq.pop_back();
Remove elements from the back of the deque where `nums[dq.back()]` is less than or equal to the current `nums[i]` because they won't contribute to the maximum score.
8 : Deque Update
dq.push_back(i);
Push the current index `i` to the deque, as it may contribute to the maximum score in future iterations.
9 : Window Size Check
Check if the current window exceeds the size `k` and adjust accordingly.
10 : Window Size Check
if(i - dq.front() >= k) dq.pop_front();
If the window size exceeds `k`, pop the front of the deque, effectively removing the index of an element that is out of range.
11 : Return Result
return nums[n - 1];
Return the maximum score at the last index of the array, which has been calculated during the iteration.
Best Case: O(n)
Average Case: O(n)
Worst Case: O(n)
Description: The algorithm processes each element exactly once, giving a time complexity of O(n).
Best Case: O(k)
Worst Case: O(k)
Description: The space complexity is O(k) due to the deque storing indices of the array.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus