解决最大乘积子数组问题

Question

我的方法有两种：

一种方法是将连续数字相乘

另一种是忽略连续的乘积，从当前数开始乘法

这是我的这种方法的代码（Python）：

class Solution:
    def maxProduct(self, nums: list[int]) -> int:
        
        def func(nums,i,rs):
            if i<0:
                return 1
            rs=nums[i]*rs
            res=max((func(nums,i-1,rs)),func(nums,i-1,rs=1))

            return res
        i=len(nums)-1
        rs=1
        return func(nums,i,rs)

    
x=Solution()

print(x.maxProduct([2,3,-2,4]))

我得到的答案应该是 6（因为最大乘积子数组是 [2,3]），但是，我得到的输出是 1。我的代码出了什么问题？？？

Answer 1

首先，你的总体思路是暴力算法。这是非常低效的，即使你修复了返回值错误的问题也无法通过 LeetCode 测试。

但是当您具体询问这些错误的输出以及导致它们的原因时，让我们来分析一下。

代码中的问题

1.总是返回1

你的基本情况——当到达

i < 0

时——总是返回1。当从递归返回时，1和1的最大值仍然是1，所以

return res

也会返回1。实际上这是不可能的递归函数可以返回 除 1 之外的任何其他值。

没关系，

rs

经常会与1不同。最终它不用来决定最终的返回值。你进行了很多乘法，最终却忽略了该乘积。

第一个修复是不忽略该产品，并在基本情况下将其返回：

            if i<0:
                return res  # Fix

现在您的代码将为示例输入返回 6。

2.缺少第三条路

应用上述修复后，您的代码将不会为其他输入返回正确的值，如下所示：

[3, -3, 4]
[-1, 1, 4]

问题是，在你对“两种方式”的分析中，缺少一种方式：就是不忽略迄今为止的产品，而是将其视为最终结果的候选者。在上面的两个示例中，4 是有效的候选者，但是通过忽略它并从新产品开始，您只会找到较少的产品（在这些示例中），并返回其中之一。这不好：4 应该有机会与其他产品进行比较。

要解决该问题，您的

max()

调用也应考虑这种“第三种方式”，并包含

rs

（无递归调用）作为

max()

的参数。这将使您的函数也适用于上述类型的输入。

3.假设 1 作为初始“产品”

还有其他输入，您的函数将返回错误的结果。例如：

[-3, 0, -2]

这里的预期输出是 0，但是你的函数将返回 1，这实际上是你永远无法从这样的输入中获得的结果。原因是您假设您可以在任何时候启动新产品时使用

rs=1

- 无论是在主调用还是在递归调用中。这通常有效，但如果涉及零则无效。所以以

rs=1

开头是错误的。始终从列表中的“实际”值开始，然后将其与邻居值相乘，或者不相乘。但不从 nums 中获取 any 值并假设 1 是解显然是错误的。要修复与主调用相关的问题，请更改此：

        i=len(nums)-1
        rs=1

...对此：

        i=len(nums)-2  # We'll exclude the last value, because...
        rs=nums[-1]    # ...we take that as a value to work with, not 1.

您需要在递归调用中进行类似的更改。改变这个：

func(nums,i-1,rs=1)

对此：

func(nums,i-1,rs=nums[i]) # Use a real value

后一个更改意味着您 

include

nums[i]，因此您应该从上面讨论的“第三种方式”中

排除

nums[i]。更正代码

将上述修复应用于您的代码后，我们得到：

    def maxProduct(self, nums: list[int]) -> int:
        def func(nums,i,rs):
            if i < 0:
                return rs # Return the product that was accumulated
            # Consider three ways:
            #   1. Stop at the current accumulated product, not including the current index
            #   2. Continue aggregating the product
            #   3. Start a new product at the current index (don't use 1)
            return max(rs, func(nums, i-1, nums[i]*rs), func(nums, i-1, rs=nums[i]))

        i = len(nums)-2  # We'll exclude the last value, because...
        rs = nums[-1]    # ...we take that as a value to work with, not 1.
        return func(nums, i, rs)

如果有足够的空间和时间资源可用，这将返回正确的响应。

蛮力还不够好

你的方法确实是一种蛮力算法。考虑所有可能的子列表，并计算和比较它们代表的产品。这效率不高，并且无法通过提供包含 50 个条目的

nums

列表的 LeetCode 测试。请注意，LeetCode 将提供最多包含 104 个条目的列表，因此 50 个确实不是很多。

此外，递归深度将成为一个问题，因为在达到较大输入的基本情况之前将达到默认堆栈限制。

你必须想出一个完全不同的算法。

提示：

如果列表没有零，那么您将需要找到一个具有
• 偶数

  个负值的子列表，因为这样乘积将为正值。在该约束内，您将希望该列表包含尽可能多的数字，因为添加更多数字不会减少乘积（同样，如果我们保留负值的数量even）。如果负值的数量是奇数，那么您需要在第一个负数之后开始计算，或者在最后一个负数之前停止。

  如果列表有零，则解决这些零之间的子列表的问题，然后查看这些子列表的最大乘积是否大于 0，否则坚持使用 0。

• 剧透解决方案：

def maxProduct(self, nums: list[int]) -> int:
     def product(start, stop):
         p = 1
         for i in range(start, stop):
             p *= nums[i]
         return p

     neg_count = start = 0  # Initialise info about first partition
     best = max(nums)  # This considers all sublists of size 1
     if nums[-1]:
         nums.append(0)  # Add a zero-stub
     for i, val in enumerate(nums):
         if val < 0:  # Track info on negative numbers in this partition
             if not neg_count:
                 first_neg_idx = i
             last_neg_idx = i
             neg_count += 1
         if val:
             continue
         # Deal with each partition delimited by zeroes
         if i - start > 1:
             if neg_count % 2 == 0: # Even negative value count
                 # Take all numbers in the partition
                 p = product(start, i)
             elif neg_count > 1:  # Odd, but not 1
                 # Either start after first negative,
                 #    or stop before last
                 p = product(first_neg_idx + 1, last_neg_idx) * min(
                         product(start, first_neg_idx + 1),
                         product(last_neg_idx, i)
                     )
             elif start == first_neg_idx:
                 # Exclude negative at start of this partition
                 p = product(start + 1, i)
             elif first_neg_idx == i - 1:
                 # Exclude negative at end of this partition
                 p = product(start, first_neg_idx)
             else:
                 # Exclude negative: choose greatest product
                 p = max(product(start, first_neg_idx),
                         product(first_neg_idx + 1, i))
             best = max(best, p)
         # Start a new partition
         start = i + 1
         neg_count = 0
     return best