Overview

This is a dynamic programming (DP) problem where you move from stone 1 to stone N by repeatedly jumping up to K steps at a time, and you want to find the maximum number of coins you can collect. We solve it efficiently using the sliding window maximum technique.

Analysis

Naive DP Approach

First, let’s consider solving this with dynamic programming.

Define \(dp[i]\) as “the maximum number of coins collected upon reaching stone \(i\).” The following recurrence holds:

\[dp[i] = \max_{j \in [\max(0, i-K), i-1]} dp[j] + A[i]\]

In other words, stone \(i\) can be reached by jumping from any of stones \(i-K\) through \(i-1\), so we choose the one with the maximum \(dp\) value.

Problem with the Naive Approach

Computing each \(dp[i]\) requires examining up to \(K\) candidates, resulting in an overall time complexity of \(O(NK)\). When \(N, K\) are up to \(2 \times 10^5\), this requires up to \(4 \times 10^{10}\) operations in the worst case, which will result in TLE (Time Limit Exceeded).

Solution: Sliding Window Maximum

We need to efficiently find “the maximum value among the previous \(K\) elements.” This can be done in \(O(1)\) (amortized) using the sliding window maximum technique (also known as a monotonic decreasing deque).

Algorithm

How the Monotonic Decreasing Deque Works

Using a deque (double-ended queue), we always maintain the following properties: - Elements in the deque are ordered in ascending order of indices - Elements in the deque are ordered in descending order of values (monotonically decreasing)

Due to these properties, the front of the deque always contains “the maximum value within the current range.”

Processing Flow

1. Initialization: \(dp[0] = A[0]\) (collect the coins on stone 1)
2. For each stone \(i\) (\(i = 1, 2, \ldots, N-1\)):
   • Remove out-of-range elements: Remove elements from the front of the deque whose index is less than \(i - K\)
   • Get the maximum: The front of the deque is the maximum value within the range, so \(dp[i] = (\text{front value}) + A[i]\)
   • Maintain monotonicity: Remove elements from the back of the deque that are less than or equal to \(dp[i]\), then add \(dp[i]\)

Concrete Example

For \(N=5, K=2, A=[3, -2, 1, 4, -1]\):

\(i\)	Reference range	Deque state	\(dp[i]\)
0	-	[(3, 0)]	3
1	[0]	[(3, 0), (1, 1)]	3 + (-2) = 1
2	[0,1]	[(4, 2)]	3 + 1 = 4
3	[1,2]	[(8, 3)]	4 + 4 = 8
4	[2,3]	[(8, 3), (7, 4)]	8 + (-1) = 7

Answer: \(dp[4] = 7\)

Complexity

• Time complexity: \(O(N)\)
  • Each element is added to and removed from the deque exactly once
• Space complexity: \(O(N)\)
  • Both the \(dp\) array and the deque hold at most \(O(N)\) elements

Implementation Notes

• Store (value, index) pairs in the deque to handle both out-of-range checks and maximum value retrieval

• When maintaining monotonicity, compare with <= so that if values are equal, the newer one is kept (either choice is correct, but be consistent)

• Be careful not to confuse 0-indexed and 1-indexed (this code uses 0-indexed)

  Source Code

from collections import deque

def solve():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    
    # dp[i] = i番目の石に到達したときの最大コイン数
    # dp[i] = max(dp[j] for j in range(max(0, i-K), i)) + A[i]
    
    # スライド最大値を使って効率化
    # dequeには (値, インデックス) を格納
    
    dp = [0] * N
    dp[0] = A[0]
    
    # 単調減少キュー（モノトニックデック）を使用
    dq = deque()
    dq.append((dp[0], 0))
    
    for i in range(1, N):
        # 範囲外になったインデックスを削除
        while dq and dq[0][1] < i - K:
            dq.popleft()
        
        # 現在の最大値を取得
        dp[i] = dq[0][0] + A[i]
        
        # 単調減少を維持するため、現在の値以下のものを後ろから削除
        while dq and dq[-1][0] <= dp[i]:
            dq.pop()
        
        dq.append((dp[i], i))
    
    print(dp[N - 1])

solve()

---

This editorial was generated by claude4.5opus.