All problems

Stepping Stones Score

Medium · dynamic programming

A line of stepping stones crosses a pond. You are given a list points where points[i] is the number of points on stone i. A slippery stone can have negative points.

You start on stone 0 and collect its points. Each jump takes you forward by at least 1 and at most k stones. You must finish on the last stone. Every stone you land on, including the first and the last, gives its points once.

Return the largest total you can collect on the way across.

Examples

Example 1

Input: points = [1, -5, 4, -2, 3], k = 2

Output: 8

Land on stones 0, 2 and 4 for 1 + 4 + 3. Landing on stone 3 as well would cost 2 points.

Example 2

Input: points = [5, -1, -1, -1, 5], k = 1

Output: 7

With jumps of exactly one stone you must land on every stone, so the total is 5 - 1 - 1 - 1 + 5.

Example 3

Input: points = [2, -6, -7, 3], k = 3

Output: 5

Jump straight from stone 0 to stone 3 and skip both bad stones.

Constraints

• 1 <= len(points) <= 10^5
• -10^4 <= points[i] <= 10^4
• 1 <= k <= len(points)