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}
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:
- Initialize a variable, maxProduct, to INT_MIN, which represents the smallest possible integer value.
- Iterate over all subarrays of size k by using two nested loops.
- The outer loop runs from 0 to n-k.
- The inner loop runs from i to i+k-1, where i is the starting index of the subarray.
- Calculate the product of the current subarray using the inner loop.
- If the product is greater than maxProduct, update maxProduct to the current product.
- 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 codeint 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 Codedef 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 codeif __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 codeint 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 kimport 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 codearr1 = [1, 5, 9, 8, 2, 4, 1, 8, 1, 2]k = 6n = len(arr1)print (findMaxProduct(arr1, n, k) )k = 4print (findMaxProduct(arr1, n, k))arr2 = [2, 5, 8, 1, 1, 3]k = 3n = 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 kusing 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!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
