Dada una array , arr[] de tamaño N y un entero positivo M , la tarea es encontrar el máximo producto del subarreglo módulo M y la longitud mínima del máximo producto del subarreglo .
Ejemplos:
Entrada: arr[] = {2, 3, 4, 2}, N = 4, M = 5
Salida:
El producto de subarreglo máximo es 4
La longitud mínima del subarreglo de producto máximo es 1
Explicación:
Los subarreglos de longitud 1 son {{2} , {3}, {4}, {2}} y su producto módulo M(= 5) son {2, 3, 4, 2} respectivamente.
Los subarreglos de longitud 2 son {{2, 3}, {3, 4}, {4, 2}} y el producto módulo M(= 5) son {1, 2, 3} respectivamente.
Los subarreglos de longitud 3 son {{2, 3, 4}, {3, 4, 2}} y el producto módulo M(= 5) son {4, 4, } respectivamente.
Los subarreglos de longitud 4 son {2, 3, 4, 2} y el módulo del producto M(= 5) es 3.
Por lo tanto, el módulo máximo del producto del subarreglo M(= 5) es 4 y la longitud más pequeña posible es 1.Entrada: arr[] = {5, 5, 5}, N = 3, M = 7
Salida:
El producto de subarreglo máximo es 6
La longitud mínima del subarreglo de producto máximo es 3
Enfoque ingenuo: el enfoque más simple es generar todos los subarreglos posibles y, para cada subarreglo, calcular su producto módulo M e imprimir el producto máximo del subarreglo y la longitud mínima de dicho subarreglo.
Complejidad de Tiempo: O(N 3 )
Espacio Auxiliar: O(1)
Enfoque eficiente: el enfoque anterior se puede optimizar calculando el producto del subarreglo en el rango [i, j] multiplicando arr[j] con el producto precalculado del subarreglo en el rango [i, j – 1] . Siga los pasos a continuación para resolver el problema:
- Inicialice dos variables, digamos ans y longitud, para almacenar el producto de subarreglo máximo y la longitud mínima del subarreglo de producto máximo.
- Iterar sobre el rango [0, N – 1] y realizar los siguientes pasos:
- Inicialice una variable, digamos producto, para almacenar el producto del subarreglo {arr[i], …, arr[j]}.
- Iterar sobre el rango [i, N-1] y actualizar el producto multiplicándolo por arr[j], es decir (producto * arr[j]) % M.
- En cada iteración, actualice ans if ans < producto y luego actualice la longitud, si la longitud > (j – i + 1).
- Finalmente, imprima el producto de subarreglo máximo obtenido en ans y la longitud mínima del subarreglo que tiene el producto máximo, longitud.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find maximum subarray product
// modulo M and minimum length of the subarray
void maxModProdSubarr(int arr[], int n, int M)
{
// Stores maximum subarray product modulo
// M and minimum length of the subarray
int ans = 0;
// Stores the minimum length of
// subarray having maximum product
int length = n;
// Traverse the array
for (int i = 0; i < n; i++) {
// Stores the product of a subarray
int product = 1;
// Calculate Subarray whose start
// index is i
for (int j = i; j < n; j++) {
// Multiply product by arr[i]
product = (product * arr[i]) % M;
// If product greater than ans
if (product > ans) {
// Update ans
ans = product;
if (length > j - i + 1) {
// Update length
length = j - i + 1;
}
}
}
}
// Print maximum subarray product mod M
cout << "Maximum subarray product is "
<< ans << endl;
// Print minimum length of subarray
// having maximum product
cout << "Minimum length of the maximum product "
<< "subarray is " << length << endl;
}
// Drivers Code
int main()
{
int arr[] = { 2, 3, 4, 2 };
int N = sizeof(arr) / sizeof(arr[0]);
int M = 5;
maxModProdSubarr(arr, N, M);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
import java.util.*;
class GFG{
// Function to find maximum subarray product
// modulo M and minimum length of the subarray
static void maxModProdSubarr(int arr[], int n, int M)
{
// Stores maximum subarray product modulo
// M and minimum length of the subarray
int ans = 0;
// Stores the minimum length of
// subarray having maximum product
int length = n;
// Traverse the array
for(int i = 0; i < n; i++)
{
// Stores the product of a subarray
int product = 1;
// Calculate Subarray whose start
// index is i
for(int j = i; j < n; j++)
{
// Multiply product by arr[i]
product = (product * arr[i]) % M;
// If product greater than ans
if (product > ans)
{
// Update ans
ans = product;
if (length > j - i + 1)
{
// Update length
length = j - i + 1;
}
}
}
}
// Print maximum subarray product mod M
System.out.println(
"Maximum subarray product is " + ans);
// Print minimum length of subarray
// having maximum product
System.out.println(
"Minimum length of the maximum " +
"product subarray is " + length);
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 2, 3, 4, 2 };
int N = arr.length;
int M = 5;
maxModProdSubarr(arr, N, M);
}
}
// This code is contributed by Kingash
Python3
# Python3 program for above approach
# Function to find maximum subarray product
# modulo M and minimum length of the subarray
def maxModProdSubarr(arr, n, M):
# Stores maximum subarray product modulo
# M and minimum length of the subarray
ans = 0
# Stores the minimum length of
# subarray having maximum product
length = n
# Traverse the array
for i in range(n):
# Stores the product of a subarray
product = 1
# Calculate Subarray whose start
# index is i
for j in range(i, n, 1):
# Multiply product by arr[i]
product = (product * arr[i]) % M
# If product greater than ans
if (product > ans):
# Update ans
ans = product
if (length > j - i + 1):
# Update length
length = j - i + 1
# Print maximum subarray product mod M
print("Maximum subarray product is", ans)
# Print minimum length of subarray
# having maximum product
print("Minimum length of the maximum product subarray is",length)
# Drivers Code
if __name__ == '__main__':
arr = [2, 3, 4, 2]
N = len(arr)
M = 5
maxModProdSubarr(arr, N, M)
# This code is contributed by ipg2016107.
C#
// C# program for above approach
using System;
class GFG{
// Function to find maximum subarray product
// modulo M and minimum length of the subarray
static void maxModProdSubarr(int[] arr, int n,
int M)
{
// Stores maximum subarray product modulo
// M and minimum length of the subarray
int ans = 0;
// Stores the minimum length of
// subarray having maximum product
int length = n;
// Traverse the array
for(int i = 0; i < n; i++)
{
// Stores the product of a subarray
int product = 1;
// Calculate Subarray whose start
// index is i
for(int j = i; j < n; j++)
{
// Multiply product by arr[i]
product = (product * arr[i]) % M;
// If product greater than ans
if (product > ans)
{
// Update ans
ans = product;
if (length > j - i + 1)
{
// Update length
length = j - i + 1;
}
}
}
}
// Print maximum subarray product mod M
Console.WriteLine(
"Maximum subarray product is " + ans);
// Print minimum length of subarray
// having maximum product
Console.WriteLine(
"Minimum length of the maximum " +
"product subarray is " + length);
}
// Driver code
static void Main()
{
int[] arr = { 2, 3, 4, 2 };
int N = arr.Length;
int M = 5;
maxModProdSubarr(arr, N, M);
}
}
// This code is contributed by code_hunt
Javascript
<script>
// javascript program for the above approach
// Function to find maximum subarray product
// modulo M and minimum length of the subarray
function maxModProdSubarr(arr , n , M)
{
// Stores maximum subarray product modulo
// M and minimum length of the subarray
var ans = 0;
// Stores the minimum length of
// subarray having maximum product
var length = n;
// Traverse the array
for (i = 0; i < n; i++) {
// Stores the product of a subarray
var product = 1;
// Calculate Subarray whose start
// index is i
for (j = i; j < n; j++) {
// Multiply product by arr[i]
product = (product * arr[i]) % M;
// If product greater than ans
if (product > ans) {
// Update ans
ans = product;
if (length > j - i + 1) {
// Update length
length = j - i + 1;
}
}
}
}
// Print maximum subarray product mod M
document.write("Maximum subarray product is " + ans+"<br/>");
// Print minimum length of subarray
// having maximum product
document.write("Minimum length of the maximum " + "product subarray is " + length);
}
// Driver Code
var arr = [ 2, 3, 4, 2 ];
var N = arr.length;
var M = 5;
maxModProdSubarr(arr, N, M);
// This code is contributed by umadevi9616.
</script>
Maximum subarray product is 4 Minimum length of the maximum product subarray is 1
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por architaggarwal023 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA