403. Gapped Subsequence Sum
A shop records its profit or loss for each of the next n days in nums. The owner may select a non-empty set of days to run a special event, but because staff need rest, two consecutive selected days can be at most k days apart (the day numbers differ by at most k). Days in between are simply skipped.
Return the largest total profit the owner can obtain from such a selection. Because the set must be non-empty, if every day loses money the answer is the least bad single day. A plain DP that looks back over k days at each step costs O(n * k); aim for O(n) or O(n log n).
Example 1
- Input:
- nums = [5,-3,-4,6,-8,7], k = 2
- Output:
- 15
- Explanation:
Pick days 0, 1, 3 and 5 (gaps 1, 2, 2): 5 - 3 + 6 + 7 = 15.
Example 2
- Input:
- nums = [-6,-2,-9], k = 3
- Output:
- -2
- Explanation:
Everything is negative and the set must be non-empty, so take just the day worth -2.
Constraints
1 ≤ nums.length ≤ 105
-104 ≤ nums[i] ≤ 104
1 ≤ k ≤ nums.length
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,600 msC++ 400 msJava 800 msJavaScript 800 msTypeScript 800 ms
Expected complexity
- Time
- O(n)
- Space
- O(n)