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

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));
    }
}
 
Ads Blocker Image Powered by Code Help Pro

Ads Blocker Detected!!!

We have detected that you are using extensions to block ads. Please support us by disabling these ads blocker.