Python program to find maximum product quadruple in an array
In this article, we will learn how to find the maximum product quadruple in an array using Python. A subsequence of size 4 is said to be a quadruple.
Example
Input: arr[] = {21, 4, 5, 2, 1, 10} Output: 4200 Explanation: 21*10*5*4 given the maximum product Input: arr[] = {-21, -4, -5, -2, -1, -10} Output: 4200
Maximum product quadruple in Python
Method 1: Using nested loops
In this method, we created four nested loops and calculated the product of every possible quadruple. Finally, returned the maximum product value.
def quadrupleProduct(arr): n = len(arr) res = -10000 for i in range(n): for j in range(i+1, n): for k in range(j+1, n): for l in range(k+1, n): if (res < arr[i]*arr[j]*arr[k]*arr[l]): res = arr[i]*arr[j]*arr[k]*arr[l] return res arr = [21, 4, 5, 2, 1, 10] print("The maximum product quadruple is: ", quadrupleProduct(arr))
Output
The maximum product quadruple is: 4200
Time Complexity: O(n^4)
Space complexity: O(1)
Method 2: By sorting the array
1. First the sort the given array in ascending.
2. Now the find the product of the last four elements and store its value in p1.
3. Now the find the product of the first four elements and store its value in p2.
4. Now the find the product of the last two elements and the first two elements and store its value in p3.
5. Finally, return the maximum value of p1, p2, p3.
def quadrupleProduct(arr): n = len(arr) arr.sort() p1 = arr[n-1]*arr[n-2]*arr[n-3]*arr[n-4] p2 = arr[0]*arr[1]*arr[2]*arr[3] p3 = arr[0]*arr[1]*arr[n-1]*arr[n-2] return max(p1, p2, p3) arr = [21, 4, 5, 2, 1, 10] print("The given array: ", str(arr)) print("The maximum product quadruple is: ", quadrupleProduct(arr)) arr1 = [-21, -4, -5, -2, -1, -10] print("The given array: ", str(arr1)) print("The maximum product quadruple is: ", quadrupleProduct(arr1)) arr2 = [-12, 18, -15, 4, 3, 10] print("The given array: ", str(arr2)) print("The maximum product quadruple is: ", quadrupleProduct(arr2))
Output
The given array: [21, 4, 5, 2, 1, 10] The maximum product quadruple is: 4200 The given array: [-21, -4, -5, -2, -1, -10] The maximum product quadruple is: 4200 The given array: [-12, 18, -15, 4, 3, 10] The maximum product quadruple is: 32400
Time complexity: O(n*logn)
Space complexity: O(1)
Also, read
Leave a Reply