最大乘积子数组

2024 年 08 月 29 日 | 阅读 9 分钟

找出包含正数和负数的数组的任何子数组的最大乘积。

示例

输入: 数组 = [6, -4, -10, 1, 2]

输出: 240 (其子数组是 [6, -4, -10])

输入: 数组 = [-2, -3, -11, 0, 61]

输出: 61 (其子数组是 [61])

方法 - 1

请按照以下说明编写此问题的代码

目标是遍历每个连续子数组，确定特定子数组元素的乘积，然后返回这些乘积中最大的可能乘积。

以下是此方法的算法方法

我们将运行一个嵌套的 Python for 循环来形成给定数组的每一个可能的子数组
然后我们将计算当前子数组元素的乘积
该函数将返回所有子数组中计算出的乘积的最大乘积值。

以下是上述算法的 Python 代码

代码

# Python program to find the Subarray having maximum product

# Defining a function that takes the array and the length of the array and returns the maximum product of the subarray
def maxProduct(array, n):

    # Initializing the variable that will store the result
    product = array[0]

    # Iterating through the array of elements
    for i in range(n):
        prod = array[i]

        # traversing through each subarray starting with the element present at the ith position of the array
        for j in range(i + 1, n):

            # Updating the product every time so that the product variable contains only the maximum product result after all the iterations
            product = max(product, prod)
            prod *= array[j]

        # updating the product for the (n - 1)th index.
        product = max(product, prod)

    return product

# Creating an array of integers ad passing it through the function
array = [-2, -3, -11, 2, -1, -2, 3, 61]
n = len(array)
print("The maximum product of one of the subarrays is:", maxProduct(array, n))

输出

The maximum product of one of the subarrays is: 24156

时间复杂度: 此方法的复杂度为 O(N^2)，其中 N 是给定数组中的元素数量。

辅助空间: 由于我们只创建了 product 和 prod 变量来存储乘积值，因此程序将占用额外空间。因此，此问题的空间复杂度为 O(1)。

方法 - 2

以下是第二种方法的思路

以下方法假设给定数组的输出将始终为正数。对于上述每种情况，答案都适用。对于包含 0, 0, 0, -10, 0, 0, 0, 0 等值的数组，此方法无效。此方法很容易改编以解决负数数组的问题。它与当前问题类似。

以当前数字乘以包含前一个数字的最小（负数）结果也可能产生最大乘积。例如，当我们在这个示例数组 "12, 3, -3, -5, -7, -3" 中遇到数字 3 时，最大乘积是乘以以 -7 和 -3 结尾的最小乘积得到的。

如果输入数组的所有整数都是负数，则使用上述方法得到最大乘积为 1。因此，如果最大乘积为 1，我们必须返回数组中的最大元素。

以下是上述思路的算法方法

我们将声明两个变量，max_product 和 min_product。max_product 将初始化为 1，min_product 变量将初始化为 1，max_ 变量将初始化为 0。
我们将运行一个从 0 到 N 的 for 循环。
如果当前整数大于 0，那么
- 我们将 max_product 设置为 min_product * array[i]。
- 并且，我们将 min_product 设置为 min_product * array[i] 和 1 之间的最小值。
- 我们将布尔变量设置为 1
否则，如果当前迭代的整数等于零
- 我们将 max_product 和 min_product 都设置为一。
否则
- 我们将 max_product 设置为 min_product * array[i] 和 1 之间的最大值
- 我们将 min_product 变量设置为 max_product * array[i]
如果 max_product 的值大于 max_ 变量的值，那么我们将更新 max_。
如果布尔标志设置为零，那么我们将返回零
如果 max_ 的值为一，即所有数组整数都是负数，那么我们将返回给定数组中的最大整数
最后，我们将返回 max_。

这是此方法的实现。

代码

# Python program to find the subarray with the maximum product

# Defining a function that takes the array of integers
# This approach assumes that the array contains at least one subarray whose product is equal to 1
def maxproduct(array):

    # Finding the length of the given array
    n = len(array)

    # Maximum positive product value for the current position
    max_product = 1

    # Minimum positive product value for the current position
    min_product = 1

    # Initializing the variable that will store the maximum product so far
    max_ = 0
    flag = 0

    # Now, we will traverse through the array.
    # We will keep updating these values after each iteration
    # max_product will always be one or the positive product value of the subarray ending with array[i]
    # max_product will always be one or the negative product value of the subarray ending with array[i]
    for i in range(0, n):

        # If the element at array[i] is positive, then we will update the max_product.
        # If the element at array[i] is negative, then we will update the min_product.
        if array[i] > 0:
            max_product = max_product * array[i]
            min_product = min(min_product * array[i], 1)
            flag = 1

        # If the element at array[i] is 0, then we cannot end the maximum product here,
        # We will change the max_product and min_product values to 0
        # Reminder of the assumption: The final answer is always greater than or equal to 1.
        elif array[i] == 0:
            max_product = 1
            min_product = 1

        # If the current integer is negative, we need to perform extra steps.
        # The max_product, in this case, can either value one or have a positive value.
        # The variable min_product can either have a value of 1 or a negative value.
        # next value of the min_product will always store the previous value of max_product * array[i]
        # next value of max_product will be equal to 1 if the prev value of min_product is equal to 1, otherwise the next max_product will have the previous value of min_product * arr[i]
        else:
            t = max_product
            max_product = max(min_product * array[i], 1)
            min_product = t * array[i]
        if (max_ < max_product):
            max_ = max_product

    if flag == 0 and max_ == 0:
        return 0
    return max_

# Creating an array of integers ad passing it through the function
array = [-2, -3, -11, 2, -1, -2, 3, 61]
n = len(array)
print("The maximum product of one of the subarrays is:", maxproduct(array))

输出

The maximum product of one of the subarrays is: 24156

时间复杂度: 此方法的复杂度是线性的，即 O(N)，其中 N 是数组中的元素数量。

辅助空间:此方法的空间复杂度是常数，即 O(1)。

高效方法

我们将遵循以下算法来解决问题

前面的方法假设提供的数组将始终具有正结果，这在数组仅包含负值时是不正确的，例如 (0, 0, -20, 0)、(0, 0, 0) 等。更新后的解决方案类似于“最大连续子数组和问题”，该问题使用最大和。

以下是此方法的逐步方法

在这里，我们将初始化三个变量，分别称为 max_、max_end_here 和 min_end_here
对于每次迭代，在那个迭代的索引处结束的最大乘积将是 (array[i], max_end_here * array[i], min_end_here[i] * array[i]) 中的最大值
同样，在该索引处结束的最小乘积将是这三个变量的最小值。
因此，我们将获得给定数组子数组的最终最大乘积值。

这是 Python 实现

代码

# Python program to find the Subarray with the maximum product

# Defining the function that will take the array of integers and the length of the array and it will return the minimum product
def maxProduct(array, n):

    # Maximum positive product end at this position
    max_end_here = array[0]

    # Minimum negative product end at this position
    min_end_here = array[0]

    # Initializing the overall maximum product value
    max_ = array[0]

    # Traversing through the input array.
    # The position at which the maximum product subarray will end will be the position of the maximum of the subarray elements,
    # The product of the current element and the maximum product value ending at the previous index, then the minimum product ending at the previous index.
    for i in range(1, n):
        t = max(max(array[i], array[i] * max_end_here),
                   array[i] * min_end_here)
        min_end_here = min(
            min(array[i], array[i] * max_end_here), array[i] * min_end_here)
        max_end_here = t
        max_ = max(max_, max_end_here)

    return max_

# Creating the array of integers and passing it to the function
array = [-2, -3, -11, 2, -1, -2, 3, 61]
n = len(array)
print("Maximum product of one of the subarray is:", maxProduct(array, n))

输出

The maximum product of one of the subarrays is: 24156

时间复杂度: 此方法的时间复杂度是线性的，因为我们正在遍历整数数组。因此，时间复杂度为 O(N)，其中 N 是数组中的元素数量。

辅助空间:此方法将占用 O(1) 的额外空间，因为我们只创建了变量。

高效方法

我们将采用一种简单的策略，即遍历并乘以组件，如果我们的结果高于已保存的乘积值，我们将存储它。如果出现“0”，则将所有先前项的乘积设置为 1，因为下一个元素将开始一个新的子数组。

但是这种方法存在问题。

当我们的数组包含异常多的负数时，问题就会出现。然后，为了得到偶数个负整数和一个正的最终乘积，我们必须去掉每一个负数。现在我们考虑子数组，我们不能去掉一个负数。要么必须去掉第一个负数，要么去掉最后一个负数。

然而，如果我们从开头遍历，只能去掉最后一个负数，而如果从结尾遍历，则可以去掉第一个负数。因此，我们将从两端遍历，进行两次遍历。我们将从提供最大乘积子数组的遍历中选择结果。

我们将去掉会产生最大乘积子数组的那个负数。

代码

# Python program to find the Subarray with the maximum product

# Defining the function that will take the array of integers and the length of the array and it will return the minimum product
def maxProduct(array, n):

    # Initializing the final product value and giving it the minimum possible value
    result = -2*10^31 - 1  
    prod = 1

    # Traversing through the input array
    # First, we will traverse in the forward direction, and then we will traverse in the reverse direction
    for i in range(n):
        prod *= array[i]

        # Updating the result value with the maximum value of the product of integers till the previous index and the product till the current index
        result = max(result, prod)  

        # If we encounter 0 in the array, we will reset the final product value to 1, as the subarray will start again from the next index. 
        if array[i] == 0:
            prod = 1  

    prod = 1

    # Traversing in the reverse direction
    for i in range(n - 1, -1, -1):
        prod *= array[i]
        result = max(result, prod)
        if array[i] == 0:
            product = 1

    return result

# Creating the array of integers and passing it to the function
array = [-2, -3, -11, 2, -1, -2, 3, 61]
n = len(array)
print("The maximum product of one of the subarrays is:", maxProduct(array, n))

输出

The maximum product of one of the subarrays is: 24156

时间复杂度: 此方法的时间复杂度是线性的，因为我们正在遍历整数数组。因此，时间复杂度为 O(N)，其中 N 是数组中的元素数量。

辅助空间:此方法将占用 O(1) 的额外空间，因为我们只创建了变量。

下一主题带 Python 代码的机器学习模型评估指标

最大乘积子数组

示例

方法 - 1

方法 - 2

高效方法

高效方法

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

Python 问题

最大乘积子数组

示例

方法 - 1

方法 - 2

高效方法

高效方法

相关帖子

使用 PyQt5 在 Python 中创建年龄计算器

Python TSP

Python Popen

使用 Python 进行 Android 开发

Borůvka 算法 - 最小生成树

使用 Python 在给定条件下遍历整个矩阵的最小初始顶点

Python 字典合并

Python 的 Pickle 模块

最佳 Python 编译器

Python 中不同排序技术的变体

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器