Dados dos arreglos arr[] y brr[] y un entero C , la tarea es encontrar la longitud máxima posible, digamos K , de los mismos subarreglos indexados tal que la suma del elemento máximo en el subarreglo de longitud K en brr[ ] con el producto entre K y la suma del subarreglo de longitud K en arr[] no excede C .
Ejemplos:
Entrada: arr[] = {2, 1, 3, 4, 5}, brr[] = {3, 6, 1, 3, 4}, C = 25
Salida: 3
Explicación: Considerando los subarreglos arr[] = { 2, 1, 3} (Suma = 6) y brr[] = {3, 6, 1} (Elemento máximo = 6), Elemento máximo + suma * K = 6 + 6 * 3 = 24, que es menor que C (= 25).Entrada: arr[] ={1, 2, 1, 6, 5, 5, 6, 1}, brr[] = {14, 8, 15, 15, 9, 10, 7, 12}, C = 40
Salida : 3
Explicación: Considerando los subarreglos arr[] = {1, 2, 1} (Suma = 4) y brr[] = {14, 8, 15} (Elemento máximo = 6), Elemento máximo + suma * K = 15 + 4 * 3 = 27, que es menor que C(= 40).
Enfoque ingenuo: el enfoque más simple es generar todos los subarreglos posibles de los dos arreglos dados y considerar todos los subarreglos indexados de manera similar de ambos arreglos y verificar la condición dada. Imprime la longitud máxima de los subarreglos que cumplen las condiciones dadas.
Complejidad de Tiempo: O(K*N 2 )
Espacio Auxiliar: O(1)
Enfoque basado en búsqueda binaria: para optimizar el enfoque anterior, la idea es usar la búsqueda binaria para encontrar el valor posible de K y encontrar la suma de cada subarreglo de longitud K utilizando la técnica de ventana deslizante . Siga los pasos a continuación para resolver el problema:
- Construya un árbol de segmentos para encontrar el valor máximo entre todos los rangos posibles .
- Realice una búsqueda binaria en el rango [0, N] para encontrar el tamaño máximo posible del subarreglo.
- Inicialice bajo como 0 y alto como N .
- Encuentre el valor de mid como (low + high)/2 .
- Verifique si es posible obtener el tamaño máximo del subarreglo como medio o no al verificar la condición dada. Si se determina que es cierto, actualice la longitud máxima como medio y bajo como (medio + 1) .
- De lo contrario, actualice alto como (mid – 1) .
- Después de completar los pasos anteriores, imprima el valor de la longitud máxima almacenada.
A continuación se muestra la implementación del enfoque anterior:
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
// 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
# 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#
// 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
Javascript
<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>
Producción:
3
Complejidad de tiempo: O(N*(log N) 2 )
Espacio auxiliar: O(N)
Enfoque eficiente: para optimizar el enfoque anterior, la idea es usar un Deque usando una cola monótona de modo que para cada subarreglo de longitud fija podamos encontrar un máximo en tiempo O(1). Para cualquier subarreglo en el rango [i, i + K – 1], la expresión del valor a calcular viene dada por:
![max(B[i, i + K - 1]) + (\sum_{j = i}^{j = i + K - 1}arr[j])*K](https://www.geeksforgeeks.org/wp-content/ql-cache/quicklatex.com-581b397afa9aefc0e5f0f56b310eebfd_l3.png "Rendered by QuickLaTeX.com")
A continuación se muestran los pasos:
- Realice la búsqueda binaria en el rango [0, N] para encontrar el tamaño máximo posible del subarreglo.
- Inicialice bajo como 0 y alto como N .
- Encuentre el valor de mid como (low + high)/2 .
- Compruebe si es posible obtener el tamaño máximo del subarreglo como medio o no como:
- Use deque para encontrar el elemento máximo en cada subarreglo de tamaño K en el arreglo brr[] .
- Encuentre el valor de la expresión y, si es como máximo C , salga de esta condición.
- De lo contrario, verifique todos los tamaños de subarreglo posibles a la mitad y si el valor de la expresión y si es como máximo C , entonces salga de esta condición.
- Devuelve false si no se cumple ninguna de las condiciones anteriores.
- Si el medio actual cumple con las condiciones dadas, actualice la longitud máxima como medio y bajo como (medio + 1) .
- De lo contrario Actualizar alto como (mediados – 1) .
- Después de los pasos anteriores, imprima el valor de la longitud máxima almacenada.
A continuación se muestra la implementación del enfoque anterior:
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
// 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
# 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#
// 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
Javascript
<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>
Producción:
3
Complejidad de tiempo: O(N*log N)
Espacio auxiliar: O(N)
Tema relacionado: Subarrays, subsecuencias y subconjuntos en array
Publicación traducida automáticamente
Artículo escrito por hemanthswarna1506 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA