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
ANSWER
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));
}
}