Dado anarray arr[] , la tarea es imprimir todos los subarreglos posibles que tengan un producto de sus elementos menor o igual a K .
Entrada: arr[] = {2, 1, 3, 4, 5, 6, 2}, K = 10
Salida: [[2], [1], [2, 1], [3], [1, 3 ], [2, 1, 3], [4], [5], [6], [2]]
Explicación:
Todos los subarreglos posibles que tienen un producto ≤ K son {2}, {1}, {2, 1}, {3}, {1, 3}, {2, 1, 3}, {4}, {5}, {6}, {2}.Entrada: arr[] = {2, 7, 1, 4}, K = 7
Salida: [[2], [7], [1], [7, 1], [4], [1, 4]]
Enfoque ingenuo: el enfoque más simple para resolver el problema es generar todos los subarreglos posibles a partir del arreglo dado y para cada subarreglo, verificar si su producto es menor o igual a K o no e imprimir en consecuencia.
Complejidad temporal: O(N 3 )
Espacio auxiliar: O(N)
Enfoque eficiente: el enfoque anterior se puede optimizar observando que:
Si el producto de todos los elementos de un subarreglo es menor o igual a K , entonces todos los subarreglos posibles de este subarreglo también tienen un producto menor o igual a K. Por lo tanto, estos subarreglos también deben incluirse en la respuesta.
Siga los pasos a continuación para resolver el problema:
- Inicialice un puntero que comience a apuntar al primer índice de la array.
- Itere sobre la array y siga calculando el producto de los elementos de la array y guárdelo en una variable, digamos multi .
- Si multi excede K: siga dividiendo multi por arr[start] y siga incrementando start hasta que multi se reduzca a ≤ K .
- Si multi ≤ K: Iterar desde el índice actual hasta start y almacenar los subarreglos en una Arraylist .
- Finalmente, una vez generados todos los subarreglos, imprima el Arraylist que contiene todos los subarreglos obtenidos.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to implement
// the above approach
#include<bits/stdc++.h>
using namespace std;
// Function to return all possible
// subarrays having product less
// than or equal to K
vector<vector<int>> maxSubArray(int arr[], int n,
int K)
{
// Store the required subarrays
vector<vector<int>> solution;
// Stores the product of
// current subarray
int multi = 1;
// Stores the starting index
// of the current subarray
int start = 0;
// Check for empty array
if (n <= 1 || K < 0)
{
return solution;
}
// Iterate over the array
for(int i = 0; i < n; i++)
{
// Calculate product
multi = multi * arr[i];
// If product exceeds K
while (multi > K)
{
// Reduce product
multi = multi / arr[start];
// Increase starting index
// of current subarray
start++;
}
// Stores the subarray elements
vector<int> list;
// Store the subarray elements
for(int j = i; j >= start; j--)
{
list.insert(list.begin(), arr[j]);
// Add the subarrays
// to the list
solution.push_back(list);
}
}
// Return the final
// list of subarrays
return solution;
}
// Driver Code
int main()
{
int arr[] = { 2, 7, 1, 4 };
int n = sizeof(arr) / sizeof(arr[0]);
int K = 7;
vector<vector<int>> v = maxSubArray(arr, n, K);
cout << "[";
bool first = true;
for(auto x : v)
{
if (!first)
{
cout << ", ";
}
else
{
first = false;
}
cout << "[";
bool ff = true;
for(int y : x)
{
if (!ff)
{
cout << ", ";
}
else
{
ff = false;
}
cout << y;
}
cout << "]";
}
cout << "]";
return 0;
}
// This code is contributed by rutvik_56
Java
// Java Program to implement
// the above approach
import java.io.*;
import java.util.*;
class GFG {
// Function to return all possible
// subarrays having product less
// than or equal to K
public static List<List<Integer> > maxSubArray(
int[] arr, int K)
{
// Store the required subarrays
List<List<Integer> > solution
= new ArrayList<>();
// Stores the product of
// current subarray
int multi = 1;
// Stores the starting index
// of the current subarray
int start = 0;
// Check for empty array
if (arr.length <= 1 || K < 0) {
return new ArrayList<>();
}
// Iterate over the array
for (int i = 0; i < arr.length; i++) {
// Calculate product
multi = multi * arr[i];
// If product exceeds K
while (multi > K) {
// Reduce product
multi = multi / arr[start];
// Increase starting index
// of current subarray
start++;
}
// Stores the subarray elements
List<Integer> list
= new ArrayList<>();
// Store the subarray elements
for (int j = i; j >= start; j--) {
list.add(0, arr[j]);
// Add the subarrays
// to the list
solution.add(
new ArrayList<>(list));
}
}
// Return the final
// list of subarrays
return solution;
}
// Driver Code
public static void main(String[] args)
{
int[] arr = { 2, 7, 1, 4 };
int K = 7;
System.out.println(maxSubArray(arr, K));
}
}
Python3
# Python3 program to implement # the above approach # Function to return all possible # subarrays having product less # than or equal to K def maxSubArray(arr, n, K): # Store the required subarrays solution = [] # Stores the product of # current subarray multi = 1 # Stores the starting index # of the current subarray start = 0 # Check for empty array if (n <= 1 or K < 0): return solution # Iterate over the array for i in range(n): # Calculate product multi = multi * arr[i] # If product exceeds K while (multi > K): # Reduce product multi = multi // arr[start] # Increase starting index # of current subarray start += 1 # Stores the subarray elements li = [] j = i # Store the subarray elements while(j >= start): li.insert(0, arr[j]) # Add the subarrays # to the li solution.append(list(li)) j -= 1 # Return the final # li of subarrays return solution # Driver Code if __name__=='__main__': arr = [ 2, 7, 1, 4 ] n = len(arr) K = 7 v = maxSubArray(arr, n, K) print(v) # This code is contributed by pratham76
C#
// C# Program to implement
// the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to return all possible
// subarrays having product less
// than or equal to K
public static List<List<int>> maxSubArray(int[] arr,
int K)
{
// Store the required subarrays
List<List<int> > solution = new List<List<int>>();
// Stores the product of
// current subarray
int multi = 1;
// Stores the starting index
// of the current subarray
int start = 0;
// Check for empty array
if (arr.Length <= 1 || K < 0)
{
return new List<List<int>>();
}
// Iterate over the array
for (int i = 0; i < arr.Length; i++)
{
// Calculate product
multi = multi * arr[i];
// If product exceeds K
while (multi > K)
{
// Reduce product
multi = multi / arr[start];
// Increase starting index
// of current subarray
start++;
}
// Stores the subarray elements
List<int> list = new List<int>();
// Store the subarray elements
for (int j = i; j >= start; j--)
{
list.Insert(0, arr[j]);
// Add the subarrays
// to the list
solution.Add(new List<int>(list));
}
}
// Return the final
// list of subarrays
return solution;
}
// Driver Code
public static void Main(String[] args)
{
int[] arr = {2, 7, 1, 4};
int K = 7;
List<List<int> > list = maxSubArray(arr, K);
foreach(List<int> i in list)
{
Console.Write("[");
foreach(int j in i)
{
Console.Write(j);
if(i.Count > 1)
Console.Write(",");
}
Console.Write("]");
}
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// js program to implement
// the above approach
// Function to return all possible
// subarrays having product less
// than or equal to K
function maxSubArray(arr, n, K)
{
// Store the required subarrays
let solution = [];
// Stores the product of
// current subarray
let multi = 1;
// Stores the starting index
// of the current subarray
let start = 0;
// Check for empty array
if (n <= 1 || K < 0)
{
return solution;
}
// Iterate over the array
for(let i = 0; i < n; i++)
{
// Calculate product
multi = multi * arr[i];
// If product exceeds K
while (multi > K)
{
// Reduce product
multi =Math.floor( multi / arr[start]);
// Increase starting index
// of current subarray
start++;
}
// Stores the subarray elements
let list = [];
// Store the subarray elements
for(let j = i; j >= start; j--)
{
list.unshift(arr[j]);
// Add the subarrays
// to the list
solution.push(list);
}
}
// Return the final
// list of subarrays
return solution;
}
// Driver Code
let arr = [ 2, 7, 1, 4 ];
let n = arr.length;
let K = 7;
let v = maxSubArray(arr, n, K);
document.write( "[");
let first = true;
for(let x=0;x< v.length;x++)
{
if (!first)
{
document.write(", ");
}
else
{
first = false;
}
document.write( "[");
let ff = true;
for(let y =0;y<v[x].length;y++)
{
if (!ff)
{
document.write(", ");
}
else
{
ff = false;
}
document.write(v[x][y]);
}
document.write("]");
}
document.write( "]");
</script>
Producción:
[[2], [7], [1], [7, 1], [4], [1, 4]]
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por rohit2sahu y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA