Best Spaced Subsequence Sum
HardSliding Window
Problem
A treasure hunter walks along a trail of caches, where nums[i] is the value (possibly negative, a trap) of cache i. She picks a non-empty set of caches to open, in trail order, but she cannot skip too far: any two consecutive caches she opens must be at most k positions apart.
Return the maximum total value she can collect.
Example 1
- Input:
- nums = [4, -3, -6, 5, -2, 7], k = 2
- Output:
- 13
Open caches 0, 1, 3, 5: 4 - 3 + 5 + 7 = 13. Gaps are 1, 2, 2. Skipping cache 1 would need a gap of 3.
Example 2
- Input:
- nums = [-5, -2, -9], k = 1
- Output:
- -2
At least one cache must be opened; the best is the single -2.
Constraints
- 1 ≤ k ≤ nums.length ≤ 10^5
- -10^4 ≤ nums[i] ≤ 10^4
Hint
Show the first hint
Let best[i] be the best total of a valid selection that ends by opening cache i. How does it relate to earlier best values?
Walkthrough
How to approach it
01Clarify before coding
- Must at least one cache be opened? Yes, so an all-negative trail returns its largest value.
- Is the gap measured in indices? Yes, consecutive chosen indices j < i need i - j ≤ k.
- Can the selection start and end anywhere? Yes.
02Brute force
Compute best[i] = nums[i] + max(0, best[j]) by scanning all j in [i - k, i - 1].
Cost: O(n·k) time; with n = 10^5 and k = 5·10^4 that is 5·10^9 steps. (Enumerating subsets is O(2^n).)
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.