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

• Python program to find pair with the greatest product in an array