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>
[[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