Overview

This problem asks us to maximize the total fruit that can be harvested from \(K\) consecutive trees. It can be solved efficiently using the sliding window technique (also known as the two-pointer method).

Analysis

Naive Approach and Its Problems

The simplest method is to calculate the sum for every consecutive interval of \(K\) trees.

• There are \(N-K+1\) possible starting positions: \(1, 2, \ldots, N-K+1\)
• Calculating the sum of each interval takes \(O(K)\)
• The overall complexity is \(O((N-K+1) \times K) = O(NK)\), which results in approximately \(10^{10}\) operations when \(N = 2 \times 10^5\), causing TLE

Key Insight

How does the sum of an interval change when we shift a consecutive interval by one position?

For example, with \(N = 5, K = 3\) and array \([2, 5, 3, 8, 1]\): - Interval \([1, 3]\): \(2 + 5 + 3 = 10\) - Interval \([2, 4]\): \(5 + 3 + 8 = 16\)

When shifting the interval one position to the right: - The leftmost element (\(A_1 = 2\)) exits - A new element (\(A_4 = 8\)) enters on the right

In other words, by subtracting one element and adding one element to the previous interval’s sum, we can calculate the next interval’s sum in \(O(1)\)!

Algorithm

We use the Sliding Window technique.

1. First, calculate the sum of the first \(K\) trees (\(A_0\) to \(A_{K-1}\)) and store it as current_sum
2. Initialize max_sum with current_sum
3. Shift the interval one position to the right at a time, repeating the following:
   • Add the new element \(A_i\)
   • Subtract the exiting element \(A_{i-K}\)
   • Update max_sum

Example: N=5, K=3, A=[2, 5, 3, 8, 1]

Initial: [2, 5, 3] → current_sum = 10, max_sum = 10
i=3:     [5, 3, 8] → current_sum = 10 - 2 + 8 = 16, max_sum = 16
i=4:     [3, 8, 1] → current_sum = 16 - 5 + 1 = 12, max_sum = 16

Answer: 16

Complexity

• Time Complexity: \(O(N)\)

  • Calculating the sum of the first \(K\) elements: \(O(K)\)
  • Sliding the window: \(O(N - K)\) iterations, each taking \(O(1)\)
  • Total: \(O(K) + O(N - K) = O(N)\)

• Space Complexity: \(O(N)\)

  • \(O(N)\) to store array \(A\)
  • Other variables use \(O(1)\)

Implementation Notes

1. Initial interval sum calculation: In Python, you can write this concisely using slicing: sum(A[:K])
2. Index management:
   • The element to add is \(A[i]\) (where \(i\) ranges from \(K\) to \(N-1\))
   • The element to remove is \(A[i-K]\)
3. Overflow prevention: Since \(A_i\) can be up to \(10^9\) and \(K\) can be up to \(2 \times 10^5\), the sum can reach approximately \(2 \times 10^{14}\). Python handles arbitrary-precision integers automatically, but in other languages, you need to use 64-bit integers

Source Code

def solve():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    
    # Calculate the sum of fruits from the first K trees
    current_sum = sum(A[:K])
    max_sum = current_sum
    
    # Use sliding window to find the maximum
    for i in range(K, N):
        # Add the new tree and remove the old tree
        current_sum += A[i] - A[i - K]
        max_sum = max(max_sum, current_sum)
    
    print(max_sum)

solve()

---

This editorial was generated by claude4.5opus.