# Searching 47

QUESTION

Given an array of n positive integers and a positive integer k, the task is to find the maximum subarray size such that all subarrays of that size have sum of elements less than k.”,

“TESTCASE_1”: “4\n1 2 10 4\n14\n###—###SEPERATOR—###—\n2”, “TESTCASE_2”: “7\n8 20 59 1 40 2 78\n12\n###—###SEPERATOR—###—\n-1”, “TESTCASE_3”: “5\n2 7 12 9 5\n30\n###—###SEPERATOR—###—\n3”, “TESTCASE_4”: “0\n###—###SEPERATOR—###—\n0”, “TESTCASE_5”: “0\n###—###SEPERATOR—###—\n0

``````import java.io.*;
// Java program to find maximum subarray size,
// such that all subarrays of that size have
// sum less than K.
import java.util.*;

class TestClass {

// Search for the maximum length of required
// subarray.
static int bsearch(int prefixsum[], int n, int k)
{

int ans = -1; // Initialize result

// Do Binary Search for largest subarray size
int left = 1, right = n;

while (left <= right) {
int mid = (left + right) / 2;

// Check for all subarrays after mid
int i;
for (i = mid; i <= n; i++) {

// Checking if all the subarrays of a size
// is less than k.
if (prefixsum[i] - prefixsum[i - mid] > k)
break;
}

// All subarrays of size mid have sum less
// than or equal to k
if (i == n + 1) {
left = mid + 1;
ans = mid;
}

// We found a subrray of size mid with sum
// greater than k
else
right = mid - 1;
}

return ans;
}

// Return the maximum subarray size, such that
// all subarray of that size have sum less than K.
static int maxSize(int arr[], int n, int k)
{

// Initialize prefix sum array as 0.
int prefixsum[] = new int[n + 1];
Arrays.fill(prefixsum, 0);

// Finding prefix sum of the array.
for (int i = 0; i < n; i++)
prefixsum[i + 1] = prefixsum[i] + arr[i];

return bsearch(prefixsum, n, k);
}

// Driver code
public static void main(String arg[])
{
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int arr[]=new int[n];
for(int i=0;i<n;i++)
arr[i]=sc.nextInt();
int k=sc.nextInt();

System.out.println(maxSize(arr, n, k));
}
}
``````