Optimal Training Schedule
A sports coach wants to optimize the training schedule for their athlete. They have a list of N days, and for each day, a certain number of training points a[i] is achievable. The athlete can only train for a contiguous block of days, and the total training points from that block must not exceed a given limit K. The coach wants to find the longest possible training block that satisfies this condition.
Your task is to help the coach by finding the maximum length of a contiguous subarray of a whose sum is less than or equal to K.
Input
The first line contains two integers N and K, separated by a space. The second line contains N integers a_1, a_2, ..., a_n, separated by spaces.
Output
Print a single integer: the maximum length of a subarray whose sum is less than or equal to K. If no such subarray exists (i.e., even a single day's training exceeds K, or N=0), output 0.
Constraints
1 <= N <= 200000 0 <= K <= 10^14 0 <= a_i <= 10^9
Example 1
5 10 3 1 4 1 5
4
The subarray [1, 4, 1] has sum 6 <= 10 and length 3. The subarray [3, 1, 4, 1] has sum 9 <= 10 and length 4. The subarray [1, 1, 5] has sum 7 <= 10 and length 3. The longest is length 4.
Example 2
3 2 5 2 3
1
No single element is <= 2, so no valid subarray exists. The maximum length is 0.
Hints
Similar problems
- Longest Subarray with Sum at Most KMedium
- Longest Subarray with Increasing SumMedium
- Maximum Subarray Sum with Fixed LengthMedium
- Longest Subarray with Limited DifferenceMedium
- Longest Subarray with At Most K Distinct ElementsMedium
- Sum of Two Adjacent ElementsMedium
More topics: Two Pointers problems, Sliding Window problems, Prefix Sums problems
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
5 10 3 1 4 1 5
3 2 5 2 3