Maximum Sum Subarray with Length Constraint
Given an array of N integers A and an integer K, find a subarray A[i..j] such that j - i + 1 <= K and the sum of its elements is maximized. If multiple subarrays yield the same maximum sum, choose the one with the smallest starting index i. If there's still a tie, choose the one with the smallest ending index j.
Input
The first line contains two integers N and K. The second line contains N integers A_1, A_2, ..., A_N.
Output
Print a single integer: the maximum sum achievable under the given constraints.
Constraints
1 <= N <= 200000, 1 <= K <= N, -10^9 <= A_i <= 10^9
Example 1
5 3 1 -2 3 4 -5
7
The subarray [3, 4] has sum 7 and length 2 <= 3. This is the maximum possible sum.
Example 2
7 2 5 -1 4 -2 3 0 1
5
The subarray [5] has sum 5 and length 1 <= 2. The subarray [4] has sum 4. The subarray [5, -1] has sum 4 and length 2 <= 2. Max sum is 5.
Hints
Similar problems
- Maximum Sum of Non-Adjacent ElementsHard
- Maximum Sum of Non-Adjacent Elements in a Circular ArrayMedium
- Count Consecutive OccurrencesEasy
- Maximum Sum of Non-Adjacent SubarraysMedium
- Count Numbers Divisible by KEasy
- Maximum Sum of Consecutive SubsegmentsMedium
More topics: Arrays problems, Dynamic Programming 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
7 2 5 -1 4 -2 3 0 1