Sometimes, we might have a problem in which we require to get the maximum product of 2 numbers from list but with a constraint of having the numbers in successions. This type of problem can occur while competitive programming. Let’s discuss certain ways in which this problem can be solved.
Method #1: Using max() + zip() + list comprehension This problem can be solved using the combination of above three function in which max function can be used to get the maximum value, zip and list comprehension doing the task of extending the logic to the whole list.
Python3
# Python3 code to demonstrate# Consecutive element maximum product# using zip() + max() + list comprehension# initializing string test_string = '2312231223124565128998'# printing original string print("The original string : " + str(test_string))# using zip() + max() + list comprehension# Consecutive element maximum producttest_string = list(test_string)res = max(int(a) * int(b) for a, b in zip(test_string, test_string[1:]))# print resultprint("The maximum consecutive product is : " + str(res)) |
The original string : 2312231223124565128998 The maximum consecutive product is : 81
Time Complexity: O(n*n) where n is the number of elements in the dictionary. The max() + zip() + list comprehension is used to perform the task and it takes O(n*n) time.
Auxiliary Space: O(1) constant additional space is required
Method #2 : Using max() + map() + operator.mul The above problem can also be solved using yet another combination of functions. In this combination, map functions performs the task of extending the logic to whole list and mul operator is used to perform the multiplication.
Python3
# Python3 code to demonstrate# Consecutive element maximum product# using max() + map() + operator.mulfrom operator import mul# initializing string test_string = '6543452345456987653234'# printing original string print("The original string : " + str(test_string))# using max() + map() + operator.mul# Consecutive element maximum productres = max(map(mul, map(int, test_string), map(int, test_string[1:])))# print resultprint("The maximum consecutive product is : " + str(res)) |
The original string : 6543452345456987653234 The maximum consecutive product is : 72
Time complexity: O(n), where n is the length of the input string test_string.
Auxiliary space: O(1), as the code uses constant extra space. The variables used to store the input string and the result are of constant size and do not increase with the size of the input.
Method #3: Using a sliding window
This method involves iterating through the list with a “sliding window” of size 2, and updating the maximum product as you go along.
Python3
def max_consecutive_product(lst): # Initialize max_product to the smallest possible value max_product = float('-inf') # Iterate through the list with a "sliding window" of size 2 for i in range(len(lst) - 1): # Calculate the product of the current pair product = lst[i] * lst[i+1] # Update max_product if necessary max_product = max(max_product, product) # Print the original list print("Original list:", lst) # Return the maximum consecutive product return max_productprint(max_consecutive_product([1, 2, 3, 4]))# Output:# Original list: [1, 2, 3, 4]# 6 (maximum product is achieved with pair (2, 3))#This code is contributed by Edula Vinay Kumar Reddy |
Original list: [1, 2, 3, 4] 12
Time complexity: O(n)
Auxiliary Space: O(1)
NumPy approach to find the maximum product of consecutive elements in a list:
Algorithm:
- Convert the input string to a NumPy array.
- Use the NumPy roll() function to create a 2D array containing all the consecutive pairs of elements in the array.
- Use the NumPy prod() function to compute the product of each pair.
- Use the NumPy max() function to find the maximum product.
Python3
import numpy as np# Function to find the maximum consecutive productdef max_consecutive_product(lst): # Convert input list to NumPy array arr = np.array(lst) # Create 2D array of consecutive pairs # using NumPy roll() pairs = np.roll(arr, -1)[:-1] pairs = np.vstack((arr[:-1], pairs)).T # Compute product of each pair using # NumPy prod() products = np.prod(pairs, axis=1) # Find maximum product using NumPy max() max_product = np.max(products) # Print original list and return # the maximum product print("Original list:", lst) return max_product# Driver Codeprint(max_consecutive_product([1, 2, 3, 4])) |
Output:
Original list: [1, 2, 3, 4] 12
Time complexity: O(n), where n is the length of the input list.
Space complexity: O(n), as the input list is converted to a NumPy array, which takes up O(n) space, and additional space is used for the pairs and products arrays, which also take up O(n) space.
METHOD 5:Using re and heapq.
APPROACH:
This program finds the maximum product of two consecutive elements in a list of integers that is given as a string.
ALGORITHM:
1.Use the re module to extract all the integers from the input string and convert them to a list.
2.Convert the list into a heap using the heapify function from the heapq module.
3.Initialize a variable max_product to negative infinity.
4.While the length of the heap is greater than 1, pop the two smallest elements from the heap using the heappop function.
5.Multiply the two elements together to get the product.
6.If the product is greater than max_product, update max_product.
7.Push the larger of the two elements back into the heap using the heappush function.
8.Once the heap has fewer than two elements, print max_product.
Python3
import reimport heapqinput_string = "Original list: [1, 2, 3, 4]"integers = [int(num) for num in re.findall(r'\d+', input_string)]heapq.heapify(integers)max_product = float('-inf')while len(integers) > 1: a = heapq.heappop(integers) b = heapq.heappop(integers) product = a * b if product > max_product: max_product = product heapq.heappush(integers, max(a, b))print("Maximum product of consecutive elements:", max_product) |
Maximum product of consecutive elements: 12
Time complexity: O(n log n)
Auxiliary Space: O(n)
