Maximum length of same indexed subarrays from two given arrays satisfying the given condition
Last Updated :
11 Jul, 2022
Given two arrays arr[] and brr[] and an integer C, the task is to find the maximum possible length, say K, of the same indexed subarrays such that the sum of the maximum element in the K-length subarray in brr[] with the product between K and sum of the K-length subarray in arr[] does not exceed C.
Examples:
Input: arr[] = {2, 1, 3, 4, 5}, brr[] = {3, 6, 1, 3, 4}, C = 25
Output: 3
Explanation: Considering the subarrays arr[] = {2, 1, 3} (Sum = 6) and brr[] = {3, 6, 1} (Maximum element = 6), Maximum element + sum * K = 6 + 6 * 3 = 24, which is less than C(= 25).
Input: arr[] ={1, 2, 1, 6, 5, 5, 6, 1}, brr[] = {14, 8, 15, 15, 9, 10, 7, 12}, C = 40
Output: 3
Explanation: Considering the subarrays arr[] = {1, 2, 1} (Sum = 4) and brr[] = {14, 8, 15} (Maximum element = 6), Maximum element + sum * K = 15 + 4 * 3 = 27, which is less than C(= 40).
Naive Approach: The simplest approach is to generate all possible subarrays of the two given arrays and consider all similarly indexed subarrays from both the arrays and check for the given condition. Print the maximum length of subarrays satisfying the given conditions.
Time Complexity: O(K*N2)
Auxiliary Space: O(1)
Binary-Search-based Approach: To optimize the above approach, the idea is to use Binary Search to find the possible value of K and to find the sum of each subarray of length K using the Sliding Window Technique. Follow the steps below to solve the problem:
- Build a Segment Tree to find the maximum value among all possible ranges.
- Perform Binary Search over the range [0, N] to find the maximum possible size of the subarray.
- Initialize low as 0 and high as N.
- Find the value of mid as (low + high)/2.
- Check if it is possible to get the maximum size of the subarray as mid or not by checking the given condition. If found to be true, then update the maximum length as mid and low as (mid + 1).
- Otherwise, update high as (mid - 1).
- After completing the above steps, print the value of the maximum length stored.
Below is the implementation of the above approach:
C++14
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Stores the segment tree node values
int seg[10000];
// Function to find maximum element
// in the given range
int getMax(int b[], int ss, int se, int qs,
int qe, int index)
{
// If the query is out of bounds
if (se < qs || ss > qe)
return INT_MIN / 2;
// If the segment is completely
// inside the query range
if (ss >= qs && se <= qe)
return seg[index];
// Calculate the mid
int mid = ss + (se - ss) / 2;
// Return maximum in left & right
// of the segment tree recursively
return max(
getMax(b, ss, mid, qs,
qe, 2 * index + 1),
getMax(b, mid + 1, se,
qs, qe, 2 * index + 2));
}
// Function to check if it is possible
// to have such a subarray of length K
bool possible(int a[], int b[], int n,
int c, int k)
{
int sum = 0;
// Check for first window of size K
for(int i = 0; i < k; i++)
{
sum += a[i];
}
// Calculate the total cost and
// check if less than equal to c
int total_cost = sum * k + getMax(
b, 0, n - 1,
0, k - 1, 0);
// If it satisfy the condition
if (total_cost <= c)
return true;
// Find the sum of current subarray
// and calculate total cost
for(int i = k; i < n; i++)
{
// Include the new element
// of current subarray
sum += a[i];
// Discard the element
// of last subarray
sum -= a[i - k];
// Calculate total cost
// and check <=c
total_cost = sum * k + getMax(
b, 0, n - 1,
i - k + 1, i, 0);
// If possible, then
// return true
if (total_cost <= c)
return true;
}
// If it is not possible
return false;
}
// Function to find maximum length
// of subarray such that sum of
// maximum element in subarray in brr[] and
// sum of subarray in arr[] * K is at most C
int maxLength(int a[], int b[], int n, int c)
{
// Base Case
if (n == 0)
return 0;
// Let maximum length be 0
int max_length = 0;
int low = 0, high = n;
// Perform Binary search
while (low <= high)
{
// Find mid value
int mid = low + (high - low) / 2;
// Check if the current mid
// satisfy the given condition
if (possible(a, b, n, c, mid) != false)
{
// If yes, then store length
max_length = mid;
low = mid + 1;
}
// Otherwise
else
high = mid - 1;
}
// Return maximum length stored
return max_length;
}
// Function that builds segment Tree
void build(int b[], int index, int s, int e)
{
// If there is only one element
if (s == e)
{
seg[index] = b[s];
return;
}
// Find the value of mid
int mid = s + (e - s) / 2;
// Build left and right parts
// of segment tree recursively
build(b, 2 * index + 1, s, mid);
build(b, 2 * index + 2, mid + 1, e);
// Update the value at current
// index
seg[index] = max(
seg[2 * index + 1],
seg[2 * index + 2]);
}
// Function that initializes the
// segment Tree
void initialiseSegmentTree(int N)
{
int seg[4 * N];
}
// Driver Code
int main()
{
int A[] = { 1, 2, 1, 6, 5, 5, 6, 1 };
int B[] = { 14, 8, 15, 15, 9, 10, 7, 12 };
int C = 40;
int N = sizeof(A) / sizeof(A[0]);
// Initialize and Build the
// Segment Tree
initialiseSegmentTree(N);
build(B, 0, 0, N - 1);
// Function Call
cout << (maxLength(A, B, N, C));
}
// This code is contributed by susmitakundugoaldanga
// Java program for the above approach
import java.io.*;
import java.util.*;
class GFG {
// Stores the segment tree node values
static int seg[];
// Function to find maximum length
// of subarray such that sum of
// maximum element in subarray in brr[] and
// sum of subarray in arr[] * K is at most C
public static int maxLength(
int a[], int b[], int n, int c)
{
// Base Case
if (n == 0)
return 0;
// Let maximum length be 0
int max_length = 0;
int low = 0, high = n;
// Perform Binary search
while (low <= high) {
// Find mid value
int mid = low + (high - low) / 2;
// Check if the current mid
// satisfy the given condition
if (possible(a, b, n, c, mid)) {
// If yes, then store length
max_length = mid;
low = mid + 1;
}
// Otherwise
else
high = mid - 1;
}
// Return maximum length stored
return max_length;
}
// Function to check if it is possible
// to have such a subarray of length K
public static boolean possible(
int a[], int b[], int n,
int c, int k)
{
int sum = 0;
// Check for first window of size K
for (int i = 0; i < k; i++) {
sum += a[i];
}
// Calculate the total cost and
// check if less than equal to c
int total_cost
= sum * k + getMax(b, 0, n - 1,
0, k - 1, 0);
// If it satisfy the condition
if (total_cost <= c)
return true;
// Find the sum of current subarray
// and calculate total cost
for (int i = k; i < n; i++) {
// Include the new element
// of current subarray
sum += a[i];
// Discard the element
// of last subarray
sum -= a[i - k];
// Calculate total cost
// and check <=c
total_cost
= sum * k
+ getMax(b, 0, n - 1,
i - k + 1, i, 0);
// If possible, then
// return true
if (total_cost <= c)
return true;
}
// If it is not possible
return false;
}
// Function that builds segment Tree
public static void build(
int b[], int index, int s, int e)
{
// If there is only one element
if (s == e) {
seg[index] = b[s];
return;
}
// Find the value of mid
int mid = s + (e - s) / 2;
// Build left and right parts
// of segment tree recursively
build(b, 2 * index + 1, s, mid);
build(b, 2 * index + 2, mid + 1, e);
// Update the value at current
// index
seg[index] = Math.max(
seg[2 * index + 1],
seg[2 * index + 2]);
}
// Function to find maximum element
// in the given range
public static int getMax(
int b[], int ss, int se, int qs,
int qe, int index)
{
// If the query is out of bounds
if (se < qs || ss > qe)
return Integer.MIN_VALUE / 2;
// If the segment is completely
// inside the query range
if (ss >= qs && se <= qe)
return seg[index];
// Calculate the mid
int mid = ss + (se - ss) / 2;
// Return maximum in left & right
// of the segment tree recursively
return Math.max(
getMax(b, ss, mid, qs,
qe, 2 * index + 1),
getMax(b, mid + 1, se,
qs, qe, 2 * index + 2));
}
// Function that initializes the
// segment Tree
public static void
initialiseSegmentTree(int N)
{
seg = new int[4 * N];
}
// Driver Code
public static void main(String[] args)
{
int A[] = { 1, 2, 1, 6, 5, 5, 6, 1 };
int B[] = { 14, 8, 15, 15, 9, 10, 7, 12 };
int C = 40;
int N = A.length;
// Initialize and Build the
// Segment Tree
initialiseSegmentTree(N);
build(B, 0, 0, N - 1);
// Function Call
System.out.println(maxLength(A, B, N, C));
}
}
# Python3 program for the above approach
import math
# Stores the segment tree node values
seg = [0 for x in range(10000)]
INT_MIN = int(-10000000)
# Function to find maximum element
# in the given range
def getMax(b, ss, se, qs, qe, index):
# If the query is out of bounds
if (se < qs or ss > qe):
return int(INT_MIN / 2)
# If the segment is completely
# inside the query range
if (ss >= qs and se <= qe):
return seg[index]
# Calculate the mid
mid = int(int(ss) + int((se - ss) / 2))
# Return maximum in left & right
# of the segment tree recursively
return max(getMax(b, ss, mid, qs,
qe, 2 * index + 1),
getMax(b, mid + 1, se, qs,
qe, 2 * index + 2))
# Function to check if it is possible
# to have such a subarray of length K
def possible(a, b, n, c, k):
sum = int(0)
# Check for first window of size K
for i in range(0, k):
sum += a[i]
# Calculate the total cost and
# check if less than equal to c
total_cost = int(sum * k +
getMax(b, 0, n - 1,
0, k - 1, 0))
# If it satisfy the condition
if (total_cost <= c):
return 1
# Find the sum of current subarray
# and calculate total cost
for i in range (k, n):
# Include the new element
# of current subarray
sum += a[i]
# Discard the element
# of last subarray
sum -= a[i - k]
# Calculate total cost
# and check <=c
total_cost = int(sum * k + getMax(
b, 0, n - 1,i - k + 1, i, 0))
# If possible, then
# return true
if (total_cost <= c):
return 1
# If it is not possible
return 0
# Function to find maximum length
# of subarray such that sum of
# maximum element in subarray in brr[] and
# sum of subarray in arr[] * K is at most C
def maxLength(a, b, n, c):
# Base Case
if (n == 0):
return 0
# Let maximum length be 0
max_length = int(0)
low = 0
high = n
# Perform Binary search
while (low <= high):
# Find mid value
mid = int(low + int((high - low) / 2))
# Check if the current mid
# satisfy the given condition
if (possible(a, b, n, c, mid) != 0):
# If yes, then store length
max_length = mid
low = mid + 1
# Otherwise
else:
high = mid - 1
# Return maximum length stored
return max_length
# Function that builds segment Tree
def build(b, index, s, e):
# If there is only one element
if (s == e):
seg[index] = b[s]
return
# Find the value of mid
mid = int(s + int((e - s) / 2))
# Build left and right parts
# of segment tree recursively
build(b, 2 * index + 1, s, mid)
build(b, 2 * index + 2, mid + 1, e)
# Update the value at current
# index
seg[index] = max(seg[2 * index + 1],
seg[2 * index + 2])
# Driver Code
A = [ 1, 2, 1, 6, 5, 5, 6, 1 ]
B = [ 14, 8, 15, 15, 9, 10, 7, 12 ]
C = int(40)
N = len(A)
# Initialize and Build the
# Segment Tree
build(B, 0, 0, N - 1)
# Function Call
print((maxLength(A, B, N, C)))
# This code is contributed by Stream_Cipher
// C# program for the above approach
using System;
class GFG{
// Stores the segment tree node values
static int[] seg;
// Function to find maximum length
// of subarray such that sum of
// maximum element in subarray in brr[] and
// sum of subarray in arr[] * K is at most C
static int maxLength(int[] a, int[] b,
int n, int c)
{
// Base Case
if (n == 0)
return 0;
// Let maximum length be 0
int max_length = 0;
int low = 0, high = n;
// Perform Binary search
while (low <= high)
{
// Find mid value
int mid = low + (high - low) / 2;
// Check if the current mid
// satisfy the given condition
if (possible(a, b, n, c, mid))
{
// If yes, then store length
max_length = mid;
low = mid + 1;
}
// Otherwise
else
high = mid - 1;
}
// Return maximum length stored
return max_length;
}
// Function to check if it is possible
// to have such a subarray of length K
static bool possible(int[] a, int[] b, int n,
int c, int k)
{
int sum = 0;
// Check for first window of size K
for(int i = 0; i < k; i++)
{
sum += a[i];
}
// Calculate the total cost and
// check if less than equal to c
int total_cost = sum * k +
getMax(b, 0, n - 1,
0, k - 1, 0);
// If it satisfy the condition
if (total_cost <= c)
return true;
// Find the sum of current subarray
// and calculate total cost
for(int i = k; i < n; i++)
{
// Include the new element
// of current subarray
sum += a[i];
// Discard the element
// of last subarray
sum -= a[i - k];
// Calculate total cost
// and check <=c
total_cost = sum * k +
getMax(b, 0, n - 1,
i - k + 1, i, 0);
// If possible, then
// return true
if (total_cost <= c)
return true;
}
// If it is not possible
return false;
}
// Function that builds segment Tree
static void build(int[] b, int index,
int s, int e)
{
// If there is only one element
if (s == e)
{
seg[index] = b[s];
return;
}
// Find the value of mid
int mid = s + (e - s) / 2;
// Build left and right parts
// of segment tree recursively
build(b, 2 * index + 1, s, mid);
build(b, 2 * index + 2, mid + 1, e);
// Update the value at current
// index
seg[index] = Math.Max(
seg[2 * index + 1],
seg[2 * index + 2]);
}
// Function to find maximum element
// in the given range
public static int getMax(int[] b, int ss,
int se, int qs,
int qe, int index)
{
// If the query is out of bounds
if (se < qs || ss > qe)
return Int32.MinValue / 2;
// If the segment is completely
// inside the query range
if (ss >= qs && se <= qe)
return seg[index];
// Calculate the mid
int mid = ss + (se - ss) / 2;
// Return maximum in left & right
// of the segment tree recursively
return Math.Max(
getMax(b, ss, mid, qs,
qe, 2 * index + 1),
getMax(b, mid + 1, se,
qs, qe, 2 * index + 2));
}
// Function that initializes the
// segment Tree
static void initialiseSegmentTree(int N)
{
seg = new int[4 * N];
}
// Driver Code
static void Main()
{
int[] A = { 1, 2, 1, 6, 5, 5, 6, 1 };
int[] B = { 14, 8, 15, 15, 9, 10, 7, 12 };
int C = 40;
int N = A.Length;
// Initialize and Build the
// Segment Tree
initialiseSegmentTree(N);
build(B, 0, 0, N - 1);
// Function Call
Console.WriteLine(maxLength(A, B, N, C));
}
}
// This code is contributed by divyesh072019
<script>
// javascript program for the above approach
// Stores the segment tree node values
var seg;
// Function to find maximum length
// of subarray such that sum of
// maximum element in subarray in brr and
// sum of subarray in arr * K is at most C
function maxLength(a , b , n , c) {
// Base Case
if (n == 0)
return 0;
// Let maximum length be 0
var max_length = 0;
var low = 0, high = n;
// Perform Binary search
while (low <= high) {
// Find mid value
var mid = low + parseInt((high - low) / 2);
// Check if the current mid
// satisfy the given condition
if (possible(a, b, n, c, mid)) {
// If yes, then store length
max_length = mid;
low = mid + 1;
}
// Otherwise
else
high = mid - 1;
}
// Return maximum length stored
return max_length;
}
// Function to check if it is possible
// to have such a subarray of length K
function possible(a , b , n , c , k) {
var sum = 0;
// Check for first window of size K
for (i = 0; i < k; i++) {
sum += a[i];
}
// Calculate the total cost and
// check if less than equal to c
var total_cost = sum * k + getMax(b, 0, n - 1, 0, k - 1, 0);
// If it satisfy the condition
if (total_cost <= c)
return true;
// Find the sum of current subarray
// and calculate total cost
for (i = k; i < n; i++) {
// Include the new element
// of current subarray
sum += a[i];
// Discard the element
// of last subarray
sum -= a[i - k];
// Calculate total cost
// and check <=c
total_cost = sum * k + getMax(b, 0, n - 1, i - k + 1, i, 0);
// If possible, then
// return true
if (total_cost <= c)
return true;
}
// If it is not possible
return false;
}
// Function that builds segment Tree
function build(b , index , s , e) {
// If there is only one element
if (s == e) {
seg[index] = b[s];
return;
}
// Find the value of mid
var mid = s + parseInt((e - s) / 2);
// Build left and right parts
// of segment tree recursively
build(b, 2 * index + 1, s, mid);
build(b, 2 * index + 2, mid + 1, e);
// Update the value at current
// index
seg[index] = Math.max(seg[2 * index + 1], seg[2 * index + 2]);
}
// Function to find maximum element
// in the given range
function getMax(b , ss , se , qs , qe , index) {
// If the query is out of bounds
if (se < qs || ss > qe)
return parseInt(Number.MIN_VALUE / 2);
// If the segment is completely
// inside the query range
if (ss >= qs && se <= qe)
return seg[index];
// Calculate the mid
var mid = ss + (se - ss) / 2;
// Return maximum in left & right
// of the segment tree recursively
return Math.max(getMax(b, ss, mid, qs, qe, 2 * index + 1), getMax(b, mid + 1, se, qs, qe, 2 * index + 2));
}
// Function that initializes the
// segment Tree
function initialiseSegmentTree(N) {
seg = Array(4 * N).fill(0);
}
// Driver Code
var A = [ 1, 2, 1, 6, 5, 5, 6, 1 ];
var B = [ 14, 8, 15, 15, 9, 10, 7, 12 ];
var C = 40;
var N = A.length;
// Initialize and Build the
// Segment Tree
initialiseSegmentTree(N);
build(B, 0, 0, N - 1);
// Function Call
document.write(maxLength(A, B, N, C));
// This code contributed by aashish1995
</script>
Time Complexity: O(N*(log N)2)
Auxiliary Space: O(N)
Efficient Approach: To optimize the above approach, the idea is to use a Deque by using a monotone queue such that for each subarray of fixed length we can find a maximum in O(1) time. For any subarray in the range [i, i + K - 1] the value expression to be calculated is given by:
max(B[i, i + K - 1]) + (\sum_{j = i}^{j = i + K - 1}arr[j])*K
Below are the steps:
- Perform the Binary Search over the range [0, N] to find the maximum possible size of the subarray.
- Initialize low as 0 and high as N.
- Find the value of mid as (low + high)/2.
- Check if it is possible to get the maximum size of the subarray as mid or not as:
- Use deque to find the maximum element in each subarray of size K in the array brr[].
- Find the value of the expression and if it at most C then break out of this condition.
- Else check for all possible subarray size mid and if the value of the expression and if it at most C then break out of this condition.
- Return false if none of the above conditions satisfies.
- If the current mid satisfies the given conditions then update maximum length as mid and low as (mid + 1).
- Else Update high as (mid - 1).
- After the above steps, print the value of the maximum length stored.
Below is the implementation of the above approach:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to check if it is possible
// to have such a subarray of length K
bool possible(int a[], int b[], int n, int c,
int k)
{
// Finds the maximum element
// in each window of size k
deque <int> dq;
// Check for window of size K
int sum = 0;
// For all possible subarrays of
// length k
for (int i = 0; i < k; i++)
{
sum += a[i];
// Until deque is empty
while (dq.size() > 0 && b[i] > b[dq.back()])
dq.pop_back();
dq.push_back(i);
}
// Calculate the total cost and
// check if less than equal to c
int total_cost = sum * k + b[dq.front()];
if (total_cost <= c)
return true;
// Find sum of current subarray
// and the total cost
for (int i = k; i < n; i++)
{
// Include the new element
// of current subarray
sum += a[i];
// Discard the element
// of last subarray
sum -= a[i - k];
// Remove all the elements
// in the old window
while (dq.size() > 0 && dq.front() <= i - k)
dq.pop_front();
while (dq.size() > 0 && b[i] > b[dq.back()])
dq.pop_back();
dq.push_back(i);
// Calculate total cost
// and check <=c
total_cost = sum * k + b[dq.front()];
// If current subarray
// length satisfies
if (total_cost <= c)
return true;
}
// If it is not possible
return false;
}
// Function to find maximum length
// of subarray such that sum of
// maximum element in subarray in brr[] and
// sum of subarray in arr[] * K is at most C
int maxLength(int a[], int b[], int n, int c)
{
// Base Case
if (n == 0)
return 0;
// Let maximum length be 0
int max_length = 0;
int low = 0, high = n;
// Perform Binary search
while (low <= high)
{
// Find mid value
int mid = low + (high - low) / 2;
// Check if the current mid
// satisfy the given condition
if (possible(a, b, n, c, mid))
{
// If yes, then store length
max_length = mid;
low = mid + 1;
}
// Otherwise
else
high = mid - 1;
}
// Return maximum length stored
return max_length;
}
// Driver Code
int main()
{
int A[] = { 1, 2, 1, 6, 5, 5, 6, 1 };
int B[] = { 14, 8, 15, 15, 9, 10, 7, 12 };
int N = sizeof(A)/sizeof(A[0]);
int C = 40;
cout << maxLength(A, B, N, C);
return 0;
}
// This code is contributed by Dharanendra L V
// Java program for the above approach
import java.io.*;
import java.util.*;
class GFG {
// Function to find maximum length
// of subarray such that sum of
// maximum element in subarray in brr[] and
// sum of subarray in arr[] * K is at most C
public static int maxLength(
int a[], int b[], int n, int c)
{
// Base Case
if (n == 0)
return 0;
// Let maximum length be 0
int max_length = 0;
int low = 0, high = n;
// Perform Binary search
while (low <= high) {
// Find mid value
int mid = low + (high - low) / 2;
// Check if the current mid
// satisfy the given condition
if (possible(a, b, n, c, mid)) {
// If yes, then store length
max_length = mid;
low = mid + 1;
}
// Otherwise
else
high = mid - 1;
}
// Return maximum length stored
return max_length;
}
// Function to check if it is possible
// to have such a subarray of length K
public static boolean possible(
int a[], int b[], int n, int c, int k)
{
// Finds the maximum element
// in each window of size k
Deque<Integer> dq
= new LinkedList<Integer>();
// Check for window of size K
int sum = 0;
// For all possible subarrays of
// length k
for (int i = 0; i < k; i++) {
sum += a[i];
// Until deque is empty
while (dq.size() > 0
&& b[i] > b[dq.peekLast()])
dq.pollLast();
dq.addLast(i);
}
// Calculate the total cost and
// check if less than equal to c
int total_cost = sum * k
+ b[dq.peekFirst()];
if (total_cost <= c)
return true;
// Find sum of current subarray
// and the total cost
for (int i = k; i < n; i++) {
// Include the new element
// of current subarray
sum += a[i];
// Discard the element
// of last subarray
sum -= a[i - k];
// Remove all the elements
// in the old window
while (dq.size() > 0
&& dq.peekFirst()
<= i - k)
dq.pollFirst();
while (dq.size() > 0
&& b[i]
> b[dq.peekLast()])
dq.pollLast();
dq.add(i);
// Calculate total cost
// and check <=c
total_cost = sum * k
+ b[dq.peekFirst()];
// If current subarray
// length satisfies
if (total_cost <= c)
return true;
}
// If it is not possible
return false;
}
// Driver Code
public static void main(String[] args)
{
int A[] = { 1, 2, 1, 6, 5, 5, 6, 1 };
int B[] = { 14, 8, 15, 15, 9, 10, 7, 12 };
int N = A.length;
int C = 40;
System.out.println(
maxLength(A, B, N, C));
}
}
# Python3 program for the above approach
# Function to find maximum length
# of subarray such that sum of
# maximum element in subarray in brr[] and
# sum of subarray in []arr * K is at most C
def maxLength(a, b, n, c):
# Base Case
if(n == 0):
return 0
# Let maximum length be 0
max_length = 0
low = 0
high = n
# Perform Binary search
while(low <= high):
# Find mid value
mid = int(low + (high - low) / 2)
# Check if the current mid
# satisfy the given condition
if(possible(a, b, n, c, mid)):
# If yes, then store length
max_length = mid
low = mid + 1
# Otherwise
else:
high = mid - 1
# Return maximum length stored
return max_length
# Function to check if it is possible
# to have such a subarray of length K
def possible(a, b, n, c, k):
# Finds the maximum element
# in each window of size k
dq = []
# Check for window of size K
Sum = 0
# For all possible subarrays of
# length k
for i in range(k):
Sum += a[i]
# Until deque is empty
while(len(dq) > 0 and b[i] > b[dq[len(dq) - 1]]):
dq.pop(len(dq) - 1)
dq.append(i)
# Calculate the total cost and
# check if less than equal to c
total_cost = Sum * k + b[dq[0]]
if(total_cost <= c):
return True
# Find sum of current subarray
# and the total cost
for i in range(k, n):
# Include the new element
# of current subarray
Sum += a[i]
# Discard the element
# of last subarray
Sum -= a[i - k]
# Remove all the elements
# in the old window
while(len(dq) > 0 and dq[0] <= i - k):
dq.pop(0)
while(len(dq) > 0 and b[i] > b[dq[len(dq) - 1]]):
dq.pop(len(dq) - 1)
dq.append(i)
# Calculate total cost
# and check <=c
total_cost = Sum * k + b[dq[0]]
# If current subarray
# length satisfies
if(total_cost <= c):
return True
# If it is not possible
return False
# Driver Code
A = [1, 2, 1, 6, 5, 5, 6, 1]
B = [14, 8, 15, 15, 9, 10, 7, 12]
N = len(A)
C = 40
print(maxLength(A, B, N, C))
# This code is contributed by avanitrachhadiya2155
// C# program for the above approach
using System;
using System.Collections.Generic;
public class GFG {
// Function to find maximum length
// of subarray such that sum of
// maximum element in subarray in brr[] and
// sum of subarray in []arr * K is at most C
public static int maxLength(
int []a, int []b, int n, int c)
{
// Base Case
if (n == 0)
return 0;
// Let maximum length be 0
int max_length = 0;
int low = 0, high = n;
// Perform Binary search
while (low <= high) {
// Find mid value
int mid = low + (high - low) / 2;
// Check if the current mid
// satisfy the given condition
if (possible(a, b, n, c, mid)) {
// If yes, then store length
max_length = mid;
low = mid + 1;
}
// Otherwise
else
high = mid - 1;
}
// Return maximum length stored
return max_length;
}
// Function to check if it is possible
// to have such a subarray of length K
public static bool possible(
int []a, int []b, int n, int c, int k)
{
// Finds the maximum element
// in each window of size k
List<int> dq
= new List<int>();
// Check for window of size K
int sum = 0;
// For all possible subarrays of
// length k
for (int i = 0; i < k; i++) {
sum += a[i];
// Until deque is empty
while (dq.Count > 0
&& b[i] > b[dq[dq.Count - 1]])
dq.RemoveAt(dq.Count - 1);
dq.Add(i);
}
// Calculate the total cost and
// check if less than equal to c
int total_cost = sum * k
+ b[dq[0]];
if (total_cost <= c)
return true;
// Find sum of current subarray
// and the total cost
for (int i = k; i < n; i++) {
// Include the new element
// of current subarray
sum += a[i];
// Discard the element
// of last subarray
sum -= a[i - k];
// Remove all the elements
// in the old window
while (dq.Count > 0
&& dq[0]
<= i - k)
dq.RemoveAt(0);
while (dq.Count > 0
&& b[i]
> b[dq[dq.Count - 1]])
dq.RemoveAt(dq.Count - 1);
dq.Add(i);
// Calculate total cost
// and check <=c
total_cost = sum * k
+ b[dq[0]];
// If current subarray
// length satisfies
if (total_cost <= c)
return true;
}
// If it is not possible
return false;
}
// Driver Code
public static void Main(String[] args)
{
int []A = { 1, 2, 1, 6, 5, 5, 6, 1 };
int []B = { 14, 8, 15, 15, 9, 10, 7, 12 };
int N = A.Length;
int C = 40;
Console.WriteLine(
maxLength(A, B, N, C));
}
}
// This code is contributed by Amit Katiyar
<script>
// Javascript program for the above approach
// Function to check if it is possible
// to have such a subarray of length K
function possible(a, b, n, c, k)
{
// Finds the maximum element
// in each window of size k
let dq = [];
// Check for window of size K
let sum = 0;
// For all possible subarrays of
// length k
for (let i = 0; i < k; i++)
{
sum += a[i];
// Until deque is empty
while (dq.length > 0 && b[i] > b[dq[dq.length - 1]])
dq.pop();
dq.push(i);
}
// Calculate the total cost and
// check if less than equal to c
let total_cost = sum * k + b[dq[0]];
if (total_cost <= c)
return true;
// Find sum of current subarray
// and the total cost
for (let i = k; i < n; i++)
{
// Include the new element
// of current subarray
sum += a[i];
// Discard the element
// of last subarray
sum -= a[i - k];
// Remove all the elements
// in the old window
while (dq.length > 0 && dq[0] <= i - k)
dq.pop();
while (dq.length > 0 && b[i] > b[dq[dq.length - 1]])
dq.pop();
dq.push(i);
// Calculate total cost
// and check <=c
total_cost = sum * k + b[dq[0]];
// If current subarray
// length satisfies
if (total_cost <= c)
return true;
}
// If it is not possible
return false;
}
// Function to find maximum length
// of subarray such that sum of
// maximum element in subarray in brr[] and
// sum of subarray in arr[] * K is at most C
function maxLength(a, b, n, c)
{
// Base Case
if (n == 0)
return 0;
// Let maximum length be 0
let max_length = 0;
let low = 0, high = n;
// Perform Binary search
while (low <= high)
{
// Find mid value
let mid = low + parseInt((high - low) / 2, 10);
// Check if the current mid
// satisfy the given condition
if (possible(a, b, n, c, mid))
{
// If yes, then store length
max_length = mid;
low = mid + 1;
}
// Otherwise
else
high = mid - 1;
}
// Return maximum length stored
return max_length;
}
let A = [ 1, 2, 1, 6, 5, 5, 6, 1 ];
let B = [ 14, 8, 15, 15, 9, 10, 7, 12 ];
let N = A.length;
let C = 40;
document.write(maxLength(A, B, N, C));
</script>
Time Complexity: O(N*log N)
Auxiliary Space: O(N)
Related Topic: Subarrays, Subsequences, and Subsets in Array
Similar Reads
Queries to find maximum sum contiguous subarrays of given length in a rotating array
Given an array arr[] of N integers and Q queries of the form {X, Y} of the following two types: If X = 1, rotate the given array to the left by Y positions.If X = 2, print the maximum sum subarray of length Y in the current state of the array. Examples: Input: N = 5, arr[] = {1, 2, 3, 4, 5}, Q = 2,
13 min read
Maximum length sub-array which satisfies the given conditions
Given a binary array arr[], the task is to find the length of the longest sub-array of the given array such that if the sub-array is divided into two equal-sized sub-arrays then both the sub-arrays either contain all 0s or all 1s. For example, the two sub-arrays must be of the form {0, 0, 0, 0} and
12 min read
Maximum length of subarray with same sum at corresponding indices from two Arrays
Given two arrays A[] and B[] both consisting of N integers, the task is to find the maximum length of subarray [i, j] such that the sum of A[i... j] is equal to B[i... j]. Examples: Input: A[] = {1, 1, 0, 1}, B[] = {0, 1, 1, 0}Output: 3Explanation: For (i, j) = (0, 2), sum of A[0... 2] = sum of B[0.
6 min read
Find maximum value of Indices of Array that satisfy the given conditions
Given an integer N (N ? 5) Then assume you have two infinite arrays X and Y where X[] is an array of element N and each element of Y[] is 2i where i is the index of the array, the task is to find two indices let's say A and B which are the maximum value of the index at which the prefix sum in X[] is
9 min read
Javascript Program for Queries to find maximum sum contiguous subarrays of given length in a rotating array
Given an array arr[] of N integers and Q queries of the form {X, Y} of the following two types: If X = 1, rotate the given array to the left by Y positions.If X = 2, print the maximum sum subarray of length Y in the current state of the array. Examples:Â Input: N = 5, arr[] = {1, 2, 3, 4, 5}, Q = 2,
5 min read
Maximize score of same-indexed subarrays selected from two given arrays
Given two arrays A[] and B[], both consisting of N positive integers, the task is to find the maximum score among all possible same-indexed subarrays in both the arrays such that the score of any subarray over the range [L, R] is calculated by the maximum of the values (AL*BL + AL + 1*BL + 1 + ... +
15+ min read
Queries to count occurrences of maximum array element in subarrays starting from given indices
Given two arrays arr[] and q[] consisting of N integers, the task is for each query q[i] is to determine the number of times the maximum array element occurs in the subarray [q[i], arr[N - 1]]. Examples: Input: arr[] = {5, 4, 5, 3, 2}, q[] = {1, 2, 3, 4, 5}Output: 2 1 1 1 1Explanation:For the first
11 min read
Maximum sum of K-length subarray consisting of same number of distinct elements as the given array
Given an array arr[] consisting of N integers and an integer K, the task is to find a subarray of size K with maximum sum and count of distinct elements same as that of the original array. Examples: Input: arr[] = {7, 7, 2, 4, 2, 7, 4, 6, 6, 6}, K = 6Output: 31Explanation: The given array consists o
15+ min read
Maximize sum of product of same-indexed elements of equal length subarrays obtained from two given arrays
Given two arrays arr[] and brr[] of size N and M integers respectively, the task is to maximize the sum of the product of the same-indexed elements of two subarrays of an equal length with the selected subarray from the array brr[] being reversed. Examples: Input: arr[] = {-1, 3, -2, 4, 5}, brr[] =
13 min read
Maximum size of sub-array that satisfies the given condition
Given an array arr[] of integers. The task is to return the length of the maximum size sub-array such that either one of the condition is satisfied: arr[k] > arr[k + 1] when k is odd and arr[k] < arr[k + 1] when k is even.arr[k] > arr[k + 1] when k is even and arr[k] < arr[k + 1] when k
6 min read