Thursday, December 5, 2024
Google search engine
HomeData Modelling & AILargest product of a subarray of size k

Largest product of a subarray of size k

Given an array consisting of n positive integers, and an integer k. Find the largest product subarray of size k, i.e., find the maximum produce of k contiguous elements in the array where k <= n.
Examples : 

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}
Recommended Practice

Brute Force Approach:

We iterate over all subarrays of size k by using two nested loops. The outer loop runs from 0 to n-k and the inner loop runs from i to i+k-1. We calculate the product of each subarray and update the maximum product found so far. Finally, we return the maximum product.

Here are the steps for above approach:

  1. Initialize a variable, maxProduct, to INT_MIN, which represents the smallest possible integer value.
  2. Iterate over all subarrays of size k by using two nested loops.
  3. The outer loop runs from 0 to n-k.
  4. The inner loop runs from i to i+k-1, where i is the starting index of the subarray.
  5. Calculate the product of the current subarray using the inner loop.
  6. If the product is greater than maxProduct, update maxProduct to the current product.
  7. Return maxProduct as the result.

Below is the code of above approach:

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)
{
    int maxProduct = INT_MIN;
    for (int i = 0; i <= n - k; i++) {
        int product = 1;
        for (int j = i; j < i + k; j++) {
            product *= arr[j];
        }
        maxProduct = max(maxProduct, product);
    }
    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




import java.util.Arrays;
 
public class Main {
    // This function returns the maximum product of a subarray of size k in the given array
    // It assumes that k is smaller than or equal to the length of the array.
    static int findMaxProduct(int[] arr, int n, int k) {
        int maxProduct = Integer.MIN_VALUE;
        for (int i = 0; i <= n - k; i++) {
            int product = 1;
            for (int j = i; j < i + k; j++) {
                product *= arr[j];
            }
            maxProduct = Math.max(maxProduct, product);
        }
        return maxProduct;
    }
 
    // Driver code
    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));
    }
}


Python3




# Python Code
def find_max_product(arr, k):
    max_product = float('-inf'# Initialize max_product to negative infinity
    n = len(arr)  # Get the length of the input array
 
    # Iterate through the array with a window of size k
    for i in range(n - k + 1):
        product = 1  # Initialize product to 1 for each subarray
        for j in range(i, i + k):
            product *= arr[j]  # Calculate the product of the subarray
        max_product = max(max_product, product)  # Update max_product if necessary
 
    return max_product  # Return the maximum product of a subarray of size k
 
# Driver code
if __name__ == "__main__":
    arr1 = [1, 5, 9, 8, 2, 4, 1, 8, 1, 2]
    k = 6
    print(find_max_product(arr1, k))  # Output 25920
 
    k = 4
    print(find_max_product(arr1, k))  # Output 1728
 
    arr2 = [2, 5, 8, 1, 1, 3]
    k = 3
    print(find_max_product(arr2, k))  # Output 80
 
# This code is contributed by guptapratik


Output

4608
720
80


Time Complexity: O(n*k), where n is the length of the input array and k is the size of the subarray for which we are finding the maximum product.
Auxiliary Space: O(1), because we are only using a constant amount of additional space to store the maximum product and the product of the current subarray.

Method 2 (Efficient: O(n)) 
We can solve it in O(n) by using the fact that product of a subarray of size k can be computed in O(1) time if we have product of previous subarray available with us. 
 

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]

In this way, we can compute the maximum k size subarray product in only one traversal. Below is C++ implementation of the idea.

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




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


Python3




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




// 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.


Javascript




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


PHP




<?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.
?>


Output

4608
720
80


Auxiliary Space: O(1), since no extra space is being used.
This article is contributed by Ashutosh Kumar. If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
 

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!

RELATED ARTICLES

Most Popular

Recent Comments