Dada una array arr[] de tamaño N , la tarea es encontrar el producto máximo de cualquier subarreglo que consta de elementos en orden estrictamente creciente o decreciente.
Ejemplos:
Entrada: arr[] = { 1, 2, 10, 8, 1, 100, 101 }
Salida: 10100
Explicación:
El subarreglo creciente con el producto máximo es {1, 100, 101}.
Por lo tanto, la salida requerida es 1 * 100 * 101.Entrada: arr[] = { 1, 5, 7, 2, 10, 12 }
Salida: 240
Enfoque ingenuo: el enfoque más simple para resolver este problema es generar todos los subarreglos posibles a partir del arreglo dado . Para cada subarreglo, verifique si los elementos presentes en el subarreglo están en orden estrictamente creciente o decreciente o no. Si se encuentra que es cierto, entonces calcule el producto de los elementos del subarreglo. Finalmente, imprima el producto máximo obtenido.
Tiempo Complejidad: O(N 2 )
Espacio Auxiliar: O(N)
Enfoque eficiente El enfoque anterior se puede optimizar recorriendo la array y, para cada subarreglo creciente o decreciente de la array dada, encuentre el producto máximo utilizando el Algoritmo de Kadane . Finalmente, imprima el máximo de todos los productos de subarreglos crecientes o decrecientes. Siga los pasos a continuación para resolver el problema:
- Inicialice una variable, digamos maxProd , para almacenar el máximo producto posible de un subarreglo creciente o decreciente del arreglo dado.
- Recorra el arreglo y calcule el subarreglo creciente o decreciente más largo , digamos subarreglo[] , cuyo índice de inicio es i .
- Calcule el producto máximo de subarreglo[] usando el Algoritmo de Kadane para el producto , diga ProdSub y actualice maxProd = max(maxProd, ProdSub) .
- Finalmente, imprima el valor maxProd .
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 find the maximum product of
// subarray in the array, arr[]
int maxSubarrayProduct(vector<int> arr, int n)
{
// Maximum positive product
// ending at the i-th index
int max_ending_here = 1;
// Minimum negative product ending
// at the current index
int min_ending_here = 1;
// Maximum product up to
// i-th index
int max_so_far = 0;
// Check if an array element
// is positive or not
int flag = 0;
// Traverse the array
for (int i = 0; i < n; i++) {
// If current element
// is positive
if (arr[i] > 0) {
// Update max_ending_here
max_ending_here
= max_ending_here * arr[i];
// Update min_ending_here
min_ending_here
= min(min_ending_here * arr[i], 1);
// Update flag
flag = 1;
}
// If current element is 0, reset
// the start index of subarray
else if (arr[i] == 0) {
// Update max_ending_here
max_ending_here = 1;
// Update min_ending_here
min_ending_here = 1;
}
// If current element is negative
else {
// Stores max_ending_here
int temp = max_ending_here;
// Update max_ending_here
max_ending_here
= max(min_ending_here * arr[i], 1);
// Update min_ending_here
min_ending_here = temp * arr[i];
}
// Update max_so_far, if needed
if (max_so_far < max_ending_here)
max_so_far = max_ending_here;
}
// If no array elements is positive
// and max_so_far is 0
if (flag == 0 && max_so_far == 0)
return 0;
return max_so_far;
}
// Function to find the maximum product of either
// increasing subarray or the decreasing subarray
int findMaxProduct(int* a, int n)
{
// Stores start index of either increasing
// subarray or the decreasing subarray
int i = 0;
// Initially assume maxProd to be 1
int maxProd = -1e9;
// Traverse the array
while (i < n) {
// Store the longest either increasing
// subarray or the decreasing subarray
// whose start index is i
vector<int> v;
v.push_back(a[i]);
// Check for increasing subarray
if (i < n - 1 && a[i] < a[i + 1]) {
// Insert elements of
// increasing subarray
while (i < n - 1 && a[i] < a[i + 1]) {
v.push_back(a[i + 1]);
i += 1;
}
}
// Check for decreasing subarray
else if (i < n - 1 && a[i] > a[i + 1]) {
// Insert elements of
// decreasing subarray
while (i < n - 1 && a[i] > a[i + 1]) {
v.push_back(a[i + 1]);
i += 1;
}
}
// Stores maximum subarray product of
// current increasing or decreasing
// subarray
int prod = maxSubarrayProduct(v, v.size());
// Update maxProd
maxProd = max(maxProd, prod);
// Update i
i++;
}
// Finally print maxProd
return maxProd;
}
// Driver Code
int main()
{
int arr[] = { 1, 2, 10, 8, 1, 100, 101 };
int N = sizeof(arr) / sizeof(arr[0]);
cout << findMaxProduct(arr, N);
return 0;
}
Java
// Java program to implement
// the above approach
import java.util.*;
class GFG
{
// Function to find the maximum product of
// subarray in the array, arr[]
static int maxSubarrayProduct(Vector<Integer> arr, int n)
{
// Maximum positive product
// ending at the i-th index
int max_ending_here = 1;
// Minimum negative product ending
// at the current index
int min_ending_here = 1;
// Maximum product up to
// i-th index
int max_so_far = 0;
// Check if an array element
// is positive or not
int flag = 0;
// Traverse the array
for (int i = 0; i < n; i++)
{
// If current element
// is positive
if (arr.get(i) > 0)
{
// Update max_ending_here
max_ending_here
= max_ending_here * arr.get(i);
// Update min_ending_here
min_ending_here
= Math.min(min_ending_here * arr.get(i), 1);
// Update flag
flag = 1;
}
// If current element is 0, reset
// the start index of subarray
else if (arr.get(i) == 0)
{
// Update max_ending_here
max_ending_here = 1;
// Update min_ending_here
min_ending_here = 1;
}
// If current element is negative
else
{
// Stores max_ending_here
int temp = max_ending_here;
// Update max_ending_here
max_ending_here
= Math.max(min_ending_here * arr.get(i), 1);
// Update min_ending_here
min_ending_here = temp * arr.get(i);
}
// Update max_so_far, if needed
if (max_so_far < max_ending_here)
max_so_far = max_ending_here;
}
// If no array elements is positive
// and max_so_far is 0
if (flag == 0 && max_so_far == 0)
return 0;
return max_so_far;
}
// Function to find the maximum product of either
// increasing subarray or the decreasing subarray
static int findMaxProduct(int[] a, int n)
{
// Stores start index of either increasing
// subarray or the decreasing subarray
int i = 0;
// Initially assume maxProd to be 1
int maxProd = 1;
// Traverse the array
while (i < n) {
// Store the longest either increasing
// subarray or the decreasing subarray
// whose start index is i
Vector<Integer> v = new Vector<>();
v.add(a[i]);
// Check for increasing subarray
if (i < n - 1 && a[i] < a[i + 1]) {
// Insert elements of
// increasing subarray
while (i < n - 1 && a[i] < a[i + 1]) {
v.add(a[i + 1]);
i += 1;
}
}
// Check for decreasing subarray
else if (i < n - 1 && a[i] > a[i + 1]) {
// Insert elements of
// decreasing subarray
while (i < n - 1 && a[i] > a[i + 1]) {
v.add(a[i + 1]);
i += 1;
}
}
// Stores maximum subarray product of
// current increasing or decreasing
// subarray
int prod = maxSubarrayProduct(v, v.size());
// Update maxProd
maxProd = Math.max(maxProd, prod);
// Update i
i++;
}
// Finally print maxProd
return maxProd;
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 1, 2, 10, 8, 1, 100, 101 };
int N = arr.length;
System.out.print(findMaxProduct(arr, N));
}
}
// This code contributed by gauravrajput1
Python3
# Python3 program to implement # the above approach # Function to find the maximum product # of subarray in the array, arr[] def maxSubarrayProduct(arr, n): # Maximum positive product # ending at the i-th index max_ending_here = 1 # Minimum negative product ending # at the current index min_ending_here = 1 # Maximum product up to # i-th index max_so_far = 0 # Check if an array element # is positive or not flag = 0 # Traverse the array for i in range(n): # If current element # is positive if (arr[i] > 0): # Update max_ending_here max_ending_here = max_ending_here * arr[i] # Update min_ending_here min_ending_here = min( min_ending_here * arr[i], 1) # Update flag flag = 1 # If current element is 0, reset # the start index of subarray elif (arr[i] == 0): # Update max_ending_here max_ending_here = 1 # Update min_ending_here min_ending_here = 1 # If current element is negative else: # Stores max_ending_here temp = max_ending_here # Update max_ending_here max_ending_here = max( min_ending_here * arr[i], 1) # Update min_ending_here min_ending_here = temp * arr[i] # Update max_so_far, if needed if (max_so_far < max_ending_here): max_so_far = max_ending_here # If no array elements is positive # and max_so_far is 0 if (flag == 0 and max_so_far == 0): return 0 return max_so_far # Function to find the maximum product # of either increasing subarray or the # decreasing subarray def findMaxProduct(a, n): # Stores start index of either # increasing subarray or the # decreasing subarray i = 0 # Initially assume maxProd to be 1 maxProd = -10**9 # Traverse the array while (i < n): # Store the longest either increasing # subarray or the decreasing subarray # whose start index is i v = [] v.append(a[i]) # Check for increasing subarray if i < n - 1 and a[i] < a[i + 1]: # Insert elements of # increasing subarray while (i < n - 1 and a[i] < a[i + 1]): v.append(a[i + 1]) i += 1 # Check for decreasing subarray elif (i < n - 1 and a[i] > a[i + 1]): # Insert elements of # decreasing subarray while (i < n - 1 and a[i] > a[i + 1]): v.append(a[i + 1]) i += 1 # Stores maximum subarray product of # current increasing or decreasing # subarray prod = maxSubarrayProduct(v, len(v)) # Update maxProd maxProd = max(maxProd, prod) # Update i i += 1 # Finally prmaxProd return maxProd # Driver Code if __name__ == '__main__': arr = [ 1, 2, 10, 8, 1, 100, 101 ] N = len(arr) print (findMaxProduct(arr, N)) # This code is contributed by mohit kumar 29
C#
// C# program to implement
// the above approach
using System;
using System.Collections.Generic;
public class GFG
{
// Function to find the maximum product of
// subarray in the array, []arr
static int maxSubarrayProduct(List<int> arr, int n)
{
// Maximum positive product
// ending at the i-th index
int max_ending_here = 1;
// Minimum negative product ending
// at the current index
int min_ending_here = 1;
// Maximum product up to
// i-th index
int max_so_far = 0;
// Check if an array element
// is positive or not
int flag = 0;
// Traverse the array
for (int i = 0; i < n; i++)
{
// If current element
// is positive
if (arr[i] > 0)
{
// Update max_ending_here
max_ending_here
= max_ending_here * arr[i];
// Update min_ending_here
min_ending_here
= Math.Min(min_ending_here * arr[i], 1);
// Update flag
flag = 1;
}
// If current element is 0, reset
// the start index of subarray
else if (arr[i] == 0)
{
// Update max_ending_here
max_ending_here = 1;
// Update min_ending_here
min_ending_here = 1;
}
// If current element is negative
else
{
// Stores max_ending_here
int temp = max_ending_here;
// Update max_ending_here
max_ending_here
= Math.Max(min_ending_here * arr[i], 1);
// Update min_ending_here
min_ending_here = temp * arr[i];
}
// Update max_so_far, if needed
if (max_so_far < max_ending_here)
max_so_far = max_ending_here;
}
// If no array elements is positive
// and max_so_far is 0
if (flag == 0 && max_so_far == 0)
return 0;
return max_so_far;
}
// Function to find the maximum product of either
// increasing subarray or the decreasing subarray
static int findMaxProduct(int[] a, int n)
{
// Stores start index of either increasing
// subarray or the decreasing subarray
int i = 0;
// Initially assume maxProd to be 1
int maxProd = 1;
// Traverse the array
while (i < n) {
// Store the longest either increasing
// subarray or the decreasing subarray
// whose start index is i
List<int> v = new List<int>();
v.Add(a[i]);
// Check for increasing subarray
if (i < n - 1 && a[i] < a[i + 1]) {
// Insert elements of
// increasing subarray
while (i < n - 1 && a[i] < a[i + 1]) {
v.Add(a[i + 1]);
i += 1;
}
}
// Check for decreasing subarray
else if (i < n - 1 && a[i] > a[i + 1]) {
// Insert elements of
// decreasing subarray
while (i < n - 1 && a[i] > a[i + 1]) {
v.Add(a[i + 1]);
i += 1;
}
}
// Stores maximum subarray product of
// current increasing or decreasing
// subarray
int prod = maxSubarrayProduct(v, v.Count);
// Update maxProd
maxProd = Math.Max(maxProd, prod);
// Update i
i++;
}
// Finally print maxProd
return maxProd;
}
// Driver Code
public static void Main(String[] args)
{
int []arr = { 1, 2, 10, 8, 1, 100, 101 };
int N = arr.Length;
Console.Write(findMaxProduct(arr, N));
}
}
// This code is contributed by shikhasingrajput
Javascript
<script>
//Javascript program for the above approach
// Function to find the maximum product of
// subarray in the array, arr[]
function maxSubarrayProduct(arr, n)
{
// Maximum positive product
// ending at the i-th index
var max_ending_here = 1;
// Minimum negative product ending
// at the current index
var min_ending_here = 1;
// Maximum product up to
// i-th index
var max_so_far = 0;
// Check if an array element
// is positive or not
var flag = 0;
// Traverse the array
for (var i = 0; i < n; i++) {
// If current element
// is positive
if (arr[i] > 0) {
// Update max_ending_here
max_ending_here
= max_ending_here * arr[i];
// Update min_ending_here
min_ending_here
= Math.min(min_ending_here * arr[i], 1);
// Update flag
flag = 1;
}
// If current element is 0, reset
// the start index of subarray
else if (arr[i] == 0) {
// Update max_ending_here
max_ending_here = 1;
// Update min_ending_here
min_ending_here = 1;
}
// If current element is negative
else {
// Stores max_ending_here
var temp = max_ending_here;
// Update max_ending_here
max_ending_here
= Math.max(min_ending_here * arr[i], 1);
// Update min_ending_here
min_ending_here = temp * arr[i];
}
// Update max_so_far, if needed
if (max_so_far < max_ending_here)
max_so_far = max_ending_here;
}
// If no array elements is positive
// and max_so_far is 0
if (flag == 0 && max_so_far == 0)
return 0;
return max_so_far;
}
// Function to find the maximum product of either
// increasing subarray or the decreasing subarray
function findMaxProduct(a, n)
{
// Stores start index of either increasing
// subarray or the decreasing subarray
var i = 0;
// Initially assume maxProd to be 1
var maxProd = -1e9;
// Traverse the array
while (i < n) {
// Store the longest either increasing
// subarray or the decreasing subarray
// whose start index is i
var v=[];
v.push(a[i]);
// Check for increasing subarray
if (i < n - 1 && a[i] < a[i + 1]) {
// Insert elements of
// increasing subarray
while (i < n - 1 && a[i] < a[i + 1]) {
v.push(a[i + 1]);
i += 1;
}
}
// Check for decreasing subarray
else if (i < n - 1 && a[i] > a[i + 1]) {
// Insert elements of
// decreasing subarray
while (i < n - 1 && a[i] > a[i + 1]) {
v.push(a[i + 1]);
i += 1;
}
}
// Stores maximum subarray product of
// current increasing or decreasing
// subarray
var prod = maxSubarrayProduct(v, v.length);
// Update maxProd
maxProd = Math.max(maxProd, prod);
// Update i
i++;
}
// Finally print maxProd
return maxProd;
}
var arr = [ 1, 2, 10, 8, 1, 100, 101 ];
var N = arr.length;
document.write(findMaxProduct(arr, N));
//This code is contributed by SoumikMondal
</script>
Producción:
10100
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Tema relacionado: Subarrays, subsecuencias y subconjuntos en array
Publicación traducida automáticamente
Artículo escrito por AmanGupta65 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA