standard code
//Brute force for max of subarray of size < k
// by generating all subarrays
//O(N*N)
max_len =0
for(int i=0 to n-1 ){
sum = 0
for ( j= i to n-1) {
sum = sum + arr[j];
if (sum <= k) max_len = MAX(max_len m, j-i+1 );
else if (sum > k) break;
}
}
if we need to find subarray than use while loop and time complexity O(2N)
//optimised by using sliding window
/*
time = O(2N)
space = O(1)
*/
l = 0
r = 0
max_len = 0
sum = 0
while( n < r){
sum = sum + arr[r];
if ( sum > k ) {
sum = sum - arr[l];
l = l + 1 ; }
if( sum <= k ) {
max_len = MAX(max_len , r - l + 1);
r = r +1 }
}
if it asking , MAX Length , then while loop can be replaced by if , TC = O(N)
//optimised by using sliding window
/*
time = O(N)
space = O(1)
*/
l = 0
r = 0
max_len = 0
sum = 0
<u>if( n < r)</u>{
sum = sum + arr[r];
if ( sum > k ) {
sum = sum - arr[l];
l = l + 1 ; }
if( sum <= k ) {
max_len = MAX(max_len , r - l + 1);
r = r +1 }
}
