Maximum Subarray Sum with Fixed Length
Given an array of N integers, find the maximum sum of a subarray of length K. A subarray is a contiguous part of an array. If there are multiple subarrays of length K with the maximum sum, return the sum of the first such subarray encountered when scanning from left to right.
Input
The first line contains two integers N and K, separated by a space. The second line contains N integers, the elements of the array, separated by spaces.
Output
Print a single integer representing the maximum subarray sum of length K.
Constraints
1 <= K <= N <= 200000. The elements of the array are integers between -10^9 and 10^9.
Example 1
5 3 1 2 3 4 5
12
Subarrays of length 3: [1,2,3] sum 6, [2,3,4] sum 9, [3,4,5] sum 12. Max is 12.
Example 2
6 2 -1 2 -3 4 -5 6
1
Subarrays of length 2: [-1,2] sum 1, [2,-3] sum -1, [-3,4] sum 1, [4,-5] sum -1, [-5,6] sum 1. Max is 1. First occurrence is from [-1,2].
Hints
Similar problems
- Sum of Two Adjacent ElementsMedium
- Optimal Training ScheduleMedium
- Sliding Window MinimumMedium
- Largest Element in PrefixMedium
- Longest Subarray with Equal HalvesMedium
- Find Minimums in Sliding WindowsMedium
More topics: Sliding Window problems, Prefix Sums problems, Queue and Deque problems
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
5 3 1 2 3 4 5
6 2 -1 2 -3 4 -5 6