Longest Subarray with Sum at Most K
Given an array of N non-negative integers A and an integer K, find the length of the longest subarray whose sum is less than or equal to K.
A subarray is a contiguous part of an array.
If multiple subarrays have the same maximum length, return the length of any one of them.
Input
The first line contains two integers N and K, separated by a space. The second line contains N space-separated non-negative integers representing the array A.
Output
Print a single integer: the length of the longest subarray with sum at most K.
Constraints
1 <= N <= 200000 0 <= K <= 10^14 0 <= A[i] <= 10^9
Example 1
5 10 1 3 2 5 4
3
The subarray [1, 3, 2] has sum 6 <= 10 and length 3. The subarray [3, 2, 5] has sum 10 <= 10 and length 3. The subarray [5, 4] has sum 9 <= 10 and length 2. The longest is length 3.
Example 2
7 5 1 1 1 1 1 1 1
5
The longest subarray with sum at most 5 is any subarray of length 5, e.g., [1, 1, 1, 1, 1].
Hints
Similar problems
- Optimal Training ScheduleMedium
- Longest Subarray with Alternating ParityMedium
- Longest Subarray with Equal HalvesMedium
- Longest Subarray with At Most K Distinct ElementsMedium
- Longest Subarray with Limited DifferenceMedium
- Count Subarrays with Distinct 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 1 3 2 5 4
7 5 1 1 1 1 1 1 1