Overview

This problem asks us to choose a consecutive \(K\)-day period from a weather sequence of length \(N\) and find the maximum number of sunny days (S) contained within it.

Analysis

A naive approach would be to count the number of sunny days for every consecutive \(K\)-day interval. However, since the maximum value of \(N\) is \(10^6\), independently computing each interval would take \(O(NK)\) time, requiring up to \(10^{12}\) operations in the worst case, which would not fit within the time limit.

To solve this problem efficiently, we need to take advantage of the overlapping portions of sunny day counts between adjacent intervals. Consecutive intervals are almost identical to the previous one — only the first day is removed and one day is appended at the end. By leveraging this property, we can update the sunny day count for each interval in constant time.

Algorithm

We solve this efficiently using the sliding window method. The specific steps are as follows:

1. Initialize the left endpoint left to 0, the current interval’s sunny day count count to 0, and the maximum value max_count to 0.
2. Move the right endpoint right from 0 to \(N-1\) one step at a time:
   • If the current day right is sunny (S), increment count by 1.
   • If the current interval length exceeds \(K\), decrement count by 1 if the day at the left endpoint left is sunny, then increment left by 1.
   • If the current interval length is exactly \(K\), update max_count.
3. Output the final max_count.

In this method, each day is processed at most twice (once for addition and once for removal), making the computation efficient.

Complexity

• Time complexity: \(O(N)\)
  • We only scan through the array once.
• Space complexity: \(O(N)\)
  • An array is needed to store the weather sequence.

Implementation Notes

• Be careful not to update the maximum value until the interval length reaches \(K\).

• Only move the left endpoint when the interval length exceeds \(K\), ensuring the interval length is always maintained at \(K\) or less.

• Checking whether the weather is S is done with a simple character comparison.

  Source Code

import sys

def main():
    data = sys.stdin.read().splitlines()
    n, k = map(int, data[0].split())
    weathers = data[1].split()
    
    count = 0
    left = 0
    max_count = 0
    
    for right in range(n):
        if weathers[right] == 'S':
            count += 1
            
        if right - left + 1 > k:
            if weathers[left] == 'S':
                count -= 1
            left += 1
            
        if right - left + 1 == k:
            max_count = max(max_count, count)
            
    print(max_count)

if __name__ == "__main__":
    main()

This editorial was generated by deepseekv3.