使用递归查找最大乘积

Question

我看到一个问题，我想知道是否有可能使用递归来解决它。它如下：

编写一种算法，当给定输入数组时，可以从这些输入中找到最大积。例如：

Input: [1, 2, 3]
Output: 6 (1*2*3)

Input: [-1, 1, 2, 3]
Output: 6 (1*2*3)

Input: [-2, -1, 1, 2, 3]
Output: 12 (-2*-1*1*2*3)

我正在尝试找到一种使用递归来解决它的方法，但是我尝试的算法不起作用。我用Java编写的算法如下

Integer[] array;
public int maximumProduct(int[] nums) {
   array=new Integer[nums.length];
   return multiply(nums, 0);
}

public int multiply(int[] nums, int i){
    if (array[i]!=null){
        return array[i];
    }
    if (i==(nums.length-1)){
        return nums[i];
    }
    int returnval=Math.max(nums[i]*multiply(nums, i+1), multiply(nums, i+1));
    array[i]=returnval;
    return returnval;

}

此算法的问题是，如果负数为偶数，则效果不佳。例如，如果nums [0] =-2，nums [1] =-1和nums [2] = 1，则乘法（nums，1）将始终返回1而不是-1，因此它将始终看到1大于1 * -2（multiple（nums，0））。但是，我不确定如何解决此问题。有什么方法可以使用递归或动态编程解决此问题？

Answer 1

如果数组中只有一个非零元素，并且恰好是负数，那么答案是0，如果输入中存在0，或者数组仅包含单个负数元素，答案就是该元素本身。

在所有其他情况下，最终答案将是肯定的。

我们首先进行线性扫描以找到负整数的数量。如果这个数字是偶数，那么答案是所有非零元素的乘积。如果否定元素的数量奇数，我们需要在答案中省略一个否定元素，以便答案是肯定的。因为我们想要最大可能的答案，所以我们要省略的数字应具有尽可能小的绝对值。因此，在所有负数中，找到一个具有最小绝对值的负数，并找到其余非零元素的乘积，这应该是答案。]

所有这些只需要对阵列进行两次线性扫描，因此运行时间为O（n）。

Answer 2

整数的最大乘积是多少？

Answer 3

这是我的解决方案-保持打开状态以进行优化并确定运行时。这是一种通用解决方案，可在列表中查找所有整数组合的乘积。

Answer 4

首先，总是在列表中找到0，将数组分解为子问题：

Answer 5

线性版本