47 | 面试题：乘积最大子序列-算法面试通关 50 讲

当前位置:　首页>> 技术小册>> 算法面试通关 50 讲

47 | 面试题：乘积最大子序列

在算法面试中，动态规划（Dynamic Programming, DP）是一个极其重要的概念，它不仅能够帮助我们解决复杂问题，还能提升解题的效率和思维深度。其中，“乘积最大子序列”问题是动态规划应用中的一个经典案例，它要求我们在一个整数数组中找出一个连续子序列，使得该子序列中所有元素的乘积达到最大。这个问题看似简单，实则蕴含了多种边界情况和优化策略，是考察面试者算法设计和分析能力的一个好题目。

问题描述

给定一个整数数组 nums，找到一个具有最大乘积的连续子数组（至少包含一个元素），返回该子数组的最大乘积。

示例

输入: nums = [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。
输入: nums = [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 的乘积是负数，而子数组必须至少包含一个元素。

分析

首先，我们需要明确几个关键点：

负数乘以负数得正数：这意味着，如果当前元素是负数，并且之前的乘积也是负数，那么将当前元素加入乘积可能会使结果变得更大。
零的特殊性：任何数与零相乘都等于零，这可能会中断当前的乘积增长序列。
动态规划的应用：我们需要记录到当前位置为止的最大乘积和最小乘积（因为考虑到负数的存在），以便在遍历过程中更新这两个值。

解决方案

基于以上分析，我们可以设计如下动态规划算法：

定义两个变量 maxProduct 和 minProduct 分别表示到当前位置为止的最大乘积和最小乘积（注意，初始时，它们都应该被初始化为数组的第一个元素，因为子序列至少包含一个元素）。
遍历数组 nums，对于每个元素 num，更新 maxProduct 和 minProduct。
- 更新 maxProduct 时，需要考虑两种情况：一是当前元素 num 自身（如果 num 大于之前的 maxProduct），二是将 num 与之前的 maxProduct 或 minProduct 相乘（因为负数乘以负数可能得到更大的正数）。
- 更新 minProduct 时，同样考虑两种情况：一是当前元素 num 自身（如果 num 小于之前的 minProduct），二是将 num 与之前的 maxProduct 或 minProduct 相乘（因为负数乘以正数可能得到更小的负数）。
遍历过程中，同时维护一个全局的最大乘积 globalMaxProduct，用于记录遍历过程中的最大乘积。

代码实现

下面是该算法的 Python 代码实现：

def maxProduct(nums):
    if not nums:
        return 0
    maxProduct = minProduct = nums[0]
    globalMaxProduct = nums[0]
    for num in nums[1:]:
        # 临时保存当前maxProduct和minProduct的值
        prevMax = maxProduct
        prevMin = minProduct
        # 更新maxProduct和minProduct
        maxProduct = max(num, prevMax * num, prevMin * num)
        minProduct = min(num, prevMax * num, prevMin * num)
        # 更新全局最大乘积
        globalMaxProduct = max(globalMaxProduct, maxProduct)
    return globalMaxProduct
# 测试样例
print(maxProduct([2,3,-2,4]))  # 输出: 6
print(maxProduct([-2,0,-1]))   # 输出: 0

复杂度分析

时间复杂度：O(n)，其中 n 是数组 nums 的长度。我们只需要遍历一次数组即可。
空间复杂度：O(1)。我们只使用了常数个变量来存储中间结果，没有使用与输入规模相关的额外空间。

进一步优化与思考

虽然上述算法已经非常高效且易于理解，但在实际面试中，面试官可能还会进一步询问是否有其他方法或优化思路。例如，可以尝试使用分治法（Divide and Conquer）来解决这个问题，虽然分治法的时间复杂度也是 O(n)，但其思想更加复杂，且在某些情况下（如数组中包含大量零时）可能不是最优选择。

此外，还可以思考如何处理数组中存在大量负数或零的情况，以及这些特殊情况如何影响算法的选择和效率。通过这些深入思考，可以进一步展现面试者的算法素养和问题解决能力。

总之，“乘积最大子序列”问题是一个典型的动态规划应用案例，它不仅考察了面试者对动态规划的理解和应用能力，还通过负数、零等特殊情况考验了面试者的边界条件处理能力和思维深度。希望通过本文的讲解，读者能够对该问题有更深入的理解和掌握。