Overview

Given \(N\) fruit trees lined up in a row, we want to find the maximum number of fruits that can be obtained by choosing \(K\) consecutive trees.

Analysis

In this problem, we need to find the maximum sum of a contiguous subsequence (subarray) consisting of \(K\) elements.

For example, if \(A = [1, 2, 3, 4, 5]\) and \(K = 3\), the possible sums of 3 consecutive elements are: - \(A[0] + A[1] + A[2] = 1 + 2 + 3 = 6\) - \(A[1] + A[2] + A[3] = 2 + 3 + 4 = 9\) - \(A[2] + A[3] + A[4] = 3 + 4 + 5 = 12\)

The maximum among these is \(12\).

If we naively compute the sum for every interval, it takes \(O(N \cdot K)\) time. Since \(N\) and \(K\) can be up to \(2 \times 10^5\), this cannot be computed within the time limit (TLE).

Therefore, we use a “sliding window (a type of two-pointer technique)” as an efficient method to compute the sum of consecutive intervals. This is a technique that leverages the sum of the previous interval to quickly compute the sum of the next interval.

For example, if the sum of an interval \([i, i+K-1]\) is known, the sum of the next interval \([i+1, i+K]\) can be computed as: $\( \text{new sum} = \text{old sum} - A[i] + A[i + K] \)$

In this way, the sum of each interval can be computed in \(O(1)\), and the entire problem can be solved in \(O(N)\).

Algorithm

1. Compute the sum of the first \(K\) elements and set it as the current maximum.
2. Then, using the sliding window approach, advance the left endpoint one by one while updating the interval sum.
3. At each step, if the interval sum is greater than the current maximum, update the maximum.
4. Output the final maximum value.

Complexity

• Time complexity: \(O(N)\)
• Space complexity: \(O(1)\) (excluding the input array)

Implementation Notes

• When computing the initial interval sum, using sum(A[:K]) allows for concise code.

• Setting the loop range to range(1, N - K + 1) ensures processing with correct indices.

• Be careful not to mix up the order of subtraction and addition when updating current_sum.

  Source Code

N, K = map(int, input().split())
A = list(map(int, input().split()))

# 最初のK個の和を計算
current_sum = sum(A[:K])
max_sum = current_sum

# スライディングウィンドウで最大値を更新
for i in range(1, N - K + 1):
    current_sum = current_sum - A[i - 1] + A[i + K - 1]
    max_sum = max(max_sum, current_sum)

print(max_sum)

This editorial was generated by qwen3-coder-480b.