text: Maximum length L such that the sum of all subarrays of length L is less than K | C ++ implementation of the approach ; Function to return the maximum sum in a subarray of size k ; k must be greater ; Compute sum of first window of size k ; Compute sums of remaining windows by removing first element of previous window and adding last element of current window . ; Function to return the length of subarray Sum of all the subarray of this length is less than or equal to K ; Binary search from l to r as all the array elements are positive so that the maximum subarray sum is monotonically increasing ; Check if the subarray sum is greater than K or not ; Update the maximum length ; Driver code
code: #include <bits/stdc++.h> NEW_LINE using namespace std ; int maxSum ( int arr [ ] , int n , int k ) { if ( n < k ) { return -1 ; } int res = 0 ; for ( int i = 0 ; i < k ; i ++ ) res += arr [ i ] ; int curr_sum = res ; for ( int i = k ; i < n ; i ++ ) { curr_sum += arr [ i ] - arr [ i - k ] ; res = max ( res , curr_sum ) ; } return res ; } int solve ( int arr [ ] , int n , int k ) { int max_len = 0 , l = 0 , r = n , m ; while ( l <= r ) { m = ( l + r ) / 2 ; if ( maxSum ( arr , n , m ) > k ) r = m - 1 ; else { l = m + 1 ; max_len = m ; } } return max_len ; } int main ( ) { int arr [ ] = { 1 , 2 , 3 , 4 , 5 } ; int n = sizeof ( arr ) / sizeof ( int ) ; int k = 10 ; cout << solve ( arr , n , k ) ; return 0 ; }