java - 使用递归查找最大乘积

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，则 multiply(nums, 1) 将始终返回 1 而不是 -1，因此它始终会看到 1在 multip(nums, 0) 处大于 1*-2。但是，我不确定如何解决这个问题。有没有办法使用递归或动态编程来解决这个问题？

Answer 1

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

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

我们首先进行线性扫描来查找负整数的数量。如果这个数字是偶数，那么答案就是所有非零元素的乘积。如果负数的个数为奇数，则需要从答案中去掉一个负数，使答案为正数。由于我们想要最大可能的答案，所以我们想要省略的数字应该具有尽可能小的绝对值。那么在所有的负数中，找到绝对值最小的一个，并求出剩下的非零元素的乘积，这应该就是答案。

所有这些只需要对数组进行两次线性扫描，因此运行时间为 O(n)。