Mayor producto de un subarreglo de tamaño k

Dada una array que consta de n enteros positivos y un entero k. Encuentre el subarreglo de producto más grande de tamaño k, es decir, encuentre el producto máximo de k elementos contiguos en el arreglo donde k <= n.
Ejemplos: 
 

Input: arr[] = {1, 5, 9, 8, 2, 4,
                 1, 8, 1, 2} 
       k = 6
Output:   4608  
The subarray is {9, 8, 2, 4, 1, 8}

Input: arr[] = {1, 5, 9, 8, 2, 4, 1, 8, 1, 2}
       k = 4
Output:   720  
The subarray is {5, 9, 8, 2}

Input: arr[] = {2, 5, 8, 1, 1, 3};
       k = 3             
Output:   80  
The subarray is {2, 5, 8}

Método 1 (Simple: O(n*k)) 
Un enfoque ingenuo sería considerar todos los subarreglos de tamaño k uno por uno. Tal enfoque requeriría dos bucles, por lo que la complejidad sería O(n*k).
Método 2 (Eficiente: O(n)) 
Podemos resolverlo en O(n) usando el hecho de que el producto de un subarreglo de tamaño k se puede calcular en O(1) tiempo si tenemos disponible el producto del subarreglo anterior . 
 

curr_product = (prev_product / arr[i-1]) * arr[i + k -1]

prev_product : Product of subarray of size k beginning 
               with arr[i-1]

curr_product : Product of subarray of size k beginning 
               with arr[i]

De esta manera, podemos calcular el producto de subarreglo de tamaño máximo k en un solo recorrido. A continuación se muestra la implementación de la idea en C++.
 

// C++ program to find the maximum product of a subarray
// of size k.
#include <bits/stdc++.h>
using namespace std;
 
// This function returns maximum product of a subarray
// of size k in given array, arr[0..n-1]. This function
// assumes that k is smaller than or equal to n.
int findMaxProduct(int arr[], int n, int k)
{
    // Initialize the MaxProduct to 1, as all elements
    // in the array are positive
    int MaxProduct = 1;
    for (int i=0; i<k; i++)
        MaxProduct *= arr[i];
 
    int prev_product = MaxProduct;
 
    // Consider every product beginning with arr[i]
    // where i varies from 1 to n-k-1
    for (int i=1; i<=n-k; i++)
    {
        int curr_product = (prev_product/arr[i-1]) *
                            arr[i+k-1];
        MaxProduct = max(MaxProduct, curr_product);
        prev_product = curr_product;
    }
 
    // Return the maximum product found
    return MaxProduct;
}
 
// Driver code
int main()
{
    int arr1[] = {1, 5, 9, 8, 2, 4, 1, 8, 1, 2};
    int k = 6;
    int n = sizeof(arr1)/sizeof(arr1[0]);
    cout << findMaxProduct(arr1, n, k) << endl;
 
    k = 4;
    cout << findMaxProduct(arr1, n, k) << endl;
 
    int arr2[] = {2, 5, 8, 1, 1, 3};
    k = 3;
    n = sizeof(arr2)/sizeof(arr2[0]);
    cout << findMaxProduct(arr2, n, k);
 
    return 0;
}

// Java program to find the maximum product of a subarray
// of size k
import java.io.*;
import java.util.*;
 
class GFG
{
    // Function returns maximum product of a subarray
    // of size k in given array, arr[0..n-1]. This function
    // assumes that k is smaller than or equal to n.
    static int findMaxProduct(int arr[], int n, int k)
    {
        // Initialize the MaxProduct to 1, as all elements
        // in the array are positive
        int MaxProduct = 1;
        for (int i=0; i<k; i++)
            MaxProduct *= arr[i];
  
        int prev_product = MaxProduct;
  
        // Consider every product beginning with arr[i]
        // where i varies from 1 to n-k-1
        for (int i=1; i<=n-k; i++)
        {
            int curr_product = (prev_product/arr[i-1]) *
                                arr[i+k-1];
            MaxProduct = Math.max(MaxProduct, curr_product);
            prev_product = curr_product;
        }
  
        // Return the maximum product found
        return MaxProduct;
    }
     
    // driver program
    public static void main (String[] args)
    {
        int arr1[] = {1, 5, 9, 8, 2, 4, 1, 8, 1, 2};
        int k = 6;
        int n = arr1.length;
        System.out.println(findMaxProduct(arr1, n, k));
  
        k = 4;
        System.out.println(findMaxProduct(arr1, n, k));
  
        int arr2[] = {2, 5, 8, 1, 1, 3};
        k = 3;
        n = arr2.length;
        System.out.println(findMaxProduct(arr2, n, k));
    }
}
 
// This code is contributed by Pramod Kumar

# Python 3 program to find the maximum
# product of a subarray of size k.
 
# This function returns maximum product
# of a subarray of size k in given array,
# arr[0..n-1]. This function assumes
# that k is smaller than or equal to n.
def findMaxProduct(arr, n, k) :
   
    # Initialize the MaxProduct to 1,
    # as all elements in the array
    # are positive
    MaxProduct = 1
    for i in range(0, k) :
        MaxProduct = MaxProduct * arr[i]
         
    prev_product = MaxProduct
  
    # Consider every product beginning
    # with arr[i] where i varies from
    # 1 to n-k-1
    for i in range(1, n - k + 1) :
        curr_product = (prev_product // arr[i-1]) * arr[i+k-1]
        MaxProduct = max(MaxProduct, curr_product)
        prev_product = curr_product
     
     
    # Return the maximum product found
    return MaxProduct
     
# Driver code
arr1 = [1, 5, 9, 8, 2, 4, 1, 8, 1, 2]
k = 6
n = len(arr1)
print (findMaxProduct(arr1, n, k) )
k = 4
print (findMaxProduct(arr1, n, k))
 
arr2 = [2, 5, 8, 1, 1, 3]
k = 3
n = len(arr2)
 
print(findMaxProduct(arr2, n, k))
 
# This code is contributed by Nikita Tiwari.

// C# program to find the maximum
// product of a subarray of size k
using System;
 
class GFG
{
    // Function returns maximum
    // product of a subarray of
    // size k in given array,
    // arr[0..n-1]. This function
    // assumes that k is smaller
    // than or equal to n.
    static int findMaxProduct(int []arr,
                              int n, int k)
    {
        // Initialize the MaxProduct
        // to 1, as all elements
        // in the array are positive
        int MaxProduct = 1;
        for (int i = 0; i < k; i++)
            MaxProduct *= arr[i];
 
        int prev_product = MaxProduct;
 
        // Consider every product beginning
        // with arr[i] where i varies from
        // 1 to n-k-1
        for (int i = 1; i <= n - k; i++)
        {
            int curr_product = (prev_product /
                                 arr[i - 1]) *
                                 arr[i + k - 1];
            MaxProduct = Math.Max(MaxProduct,
                                  curr_product);
            prev_product = curr_product;
        }
 
        // Return the maximum
        // product found
        return MaxProduct;
    }
     
    // Driver Code
    public static void Main ()
    {
        int []arr1 = {1, 5, 9, 8, 2,
                      4, 1, 8, 1, 2};
        int k = 6;
        int n = arr1.Length;
        Console.WriteLine(findMaxProduct(arr1, n, k));
 
        k = 4;
        Console.WriteLine(findMaxProduct(arr1, n, k));
 
        int []arr2 = {2, 5, 8, 1, 1, 3};
        k = 3;
        n = arr2.Length;
        Console.WriteLine(findMaxProduct(arr2, n, k));
    }
}
 
// This code is contributed by anuj_67.

<?php
// PHP program to find the maximum
// product of a subarray of size k.
 
// This function returns maximum
// product of a subarray of size
// k in given array, arr[0..n-1].
// This function assumes that k
// is smaller than or equal to n.
function findMaxProduct( $arr, $n, $k)
{
     
    // Initialize the MaxProduct to
    // 1, as all elements
    // in the array are positive
    $MaxProduct = 1;
    for($i = 0; $i < $k; $i++)
        $MaxProduct *= $arr[$i];
 
    $prev_product = $MaxProduct;
 
    // Consider every product
    // beginning with arr[i]
    // where i varies from 1
    // to n-k-1
    for($i = 1; $i < $n - $k; $i++)
    {
        $curr_product = ($prev_product / $arr[$i - 1]) *
                                       $arr[$i + $k - 1];
        $MaxProduct = max($MaxProduct, $curr_product);
        $prev_product = $curr_product;
    }
 
    // Return the maximum
    // product found
    return $MaxProduct;
}
 
    // Driver code
    $arr1 = array(1, 5, 9, 8, 2, 4, 1, 8, 1, 2);
    $k = 6;
    $n = count($arr1);
    echo findMaxProduct($arr1, $n, $k),"\n" ;
 
    $k = 4;
    echo findMaxProduct($arr1, $n, $k),"\n";
 
    $arr2 = array(2, 5, 8, 1, 1, 3);
    $k = 3;
    $n = count($arr2);
    echo findMaxProduct($arr2, $n, $k);
 
// This code is contributed by anuj_67.
?>

<script>
 
    // JavaScript program to find the maximum
    // product of a subarray of size k
     
    // Function returns maximum
    // product of a subarray of
    // size k in given array,
    // arr[0..n-1]. This function
    // assumes that k is smaller
    // than or equal to n.
    function findMaxProduct(arr, n, k)
    {
        // Initialize the MaxProduct
        // to 1, as all elements
        // in the array are positive
        let MaxProduct = 1;
        for (let i = 0; i < k; i++)
            MaxProduct *= arr[i];
   
        let prev_product = MaxProduct;
   
        // Consider every product beginning
        // with arr[i] where i varies from
        // 1 to n-k-1
        for (let i = 1; i <= n - k; i++)
        {
            let curr_product =
            (prev_product / arr[i - 1]) * arr[i + k - 1];
            MaxProduct = Math.max(MaxProduct, curr_product);
            prev_product = curr_product;
        }
   
        // Return the maximum
        // product found
        return MaxProduct;
    }
     
    let arr1 = [1, 5, 9, 8, 2, 4, 1, 8, 1, 2];
    let k = 6;
    let n = arr1.length;
    document.write(findMaxProduct(arr1, n, k) + "</br>");
 
    k = 4;
    document.write(findMaxProduct(arr1, n, k) + "</br>");
 
    let arr2 = [2, 5, 8, 1, 1, 3];
    k = 3;
    n = arr2.length;
    document.write(findMaxProduct(arr2, n, k) + "</br>");
     
</script>

Producción:  

4608
720
80

Este artículo es una contribución de Ashutosh Kumar . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.