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.

Powered By
CHP Adblock Detector Plugin | Codehelppro