Function for calculating the maximum sum of a subarray with a length constraint

Go Hard functions

Task «Function for calculating the maximum sum of a subarray with a length constraint»

Write a function `MaxSubarraySumWithLimit(nums []int, k int) int` that takes an integer array `nums` and an integer `k` (1 ≤ k ≤ len(nums)). The function should return the maximum sum of a contiguous subarray of length at most k. If the array is empty, return 0. Implement an algorithm with time complexity O(n).

Input Format

Two numbers are given as input: n (the length of the array, 0 ≤ n ≤ 10^5) and k (1 ≤ k ≤ n). Then n integers — the elements of the array (-10^9 ≤ nums[i] ≤ 10^9).

Output Format

One integer — the maximum sum of a subarray of length at most k.

Examples

Example 1

INPUT

5 3
1 2 3 4 5

OUTPUT

12

Example 2

INPUT

4 2
-1 -2 -3 -4

OUTPUT

-1

Example 3

INPUT

7
1 2 3 4 5 -1 6

OUTPUT

6

Example 4

INPUT

6 4
2 -1 3 4 -2 1

OUTPUT

8

Example 5

INPUT

3
-5 10 20

OUTPUT

15

main.go