1278. Ring Window Best
A circular running track has n checkpoints, and nums[i] is the score awarded at checkpoint i; scores can be negative for hazards. A runner may start at any checkpoint and must visit exactly k checkpoints in a row, moving forward, and the track wraps around so that checkpoint n - 1 is followed by checkpoint 0.
Return the largest total score the runner can collect over such a stretch of k consecutive checkpoints, wrapping allowed. Compute the sum of the first window, then slide it one step at a time through all n starting positions, adding the entering checkpoint and removing the leaving one. The answer is a 64-bit integer. Aim for O(n) time and O(1) extra space.
Example 1
- Input:
- nums = [5,-1,-1,5], k = 2
- Output:
- 10
- Explanation:
The window made of the last and first checkpoints wraps around and scores 5 + 5 = 10.
Example 2
- Input:
- nums = [1,2,3], k = 2
- Output:
- 5
- Explanation:
The windows score 3, 5 and 4 (the last one wraps), so the best is 5.
Constraints
1 ≤ k ≤ nums.length ≤ 1000
-106 ≤ nums[i] ≤ 106
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Expected complexity
- Time
- O(n)
- Space
- O(1)