整数的最大乘积是多少？

要获得最大和，您需要将所有正整数乘以最大负整数的乘积，乘积中包含的负整数的个数应为偶数以获得最终的正结果。

在用于单个遍历的算法中

我将分别处理输入中的正整数和负整数。您将要保持到目前为止找到的正整数的运行积，负整数和最大的负整数（即，具有最小绝对值的负整数）的运行积。 让我们忽略最终答案为

//Initialization
int [] nums // Input
int posProduct = 1;
int negProduct = 1;
int smallestNeg = 1;

//Input Traversal
for (int i : nums) {
  if ( i == 0 ) {
    // ignore
  } else if ( i < 0 ) {
    if (smallestNeg == 1) {
      smallestNeg = i;
    } else if ( i > smallestNeg ) {
      negProduct *= smallestNeg; //Integrate the old smallest into the running product
      smallestNeg = i;           // i is the new smallest
    } else {
      negProduct *= i;
    }
  } else {
    // i is strictly positive
    posProduct *= i;
  }
}

//Result Computation
int result = posProduct;
if ( negProduct < 0 ) {
  // The running product of negative number numbers is negative
  // We use the smallestNeg to turn it back up to a positive product
  result *= smallestNeg;
  result *= negProduct;
} else {
  result *= negProduct
}

编辑：在递归遍历中

我个人发现以递归方式编写数组遍历很笨拙，但是可以做到。 为了使练习更美观，并实际回答OP的问题，以下是我的操作方法。

public class RecursiveSolver {
  public static int findMaxProduct (int [] nums) {
    return recursiveArrayTraversal(1,1,nums,0); 
  }

  private static int recursiveArrayTraversal(int posProduct,int negProduct,int smallestNeg,int [] nums,int index) {
    if (index == nums.length) {
      // End of the recursion,we traversed the whole array
      posProduct *= negProduct;
      if (posProduct < 0) {
        posProduct *= smallestNeg;
      }
      return posProduct;
    }

    // Processing the "index" element of the array
    int i = nums[index];
    if ( i == 0 ) {
      // ignore
    } else if ( i < 0 ) {
      if (smallestNeg == 1) {
        smallestNeg = i;
      } else if ( i > smallestNeg ) {
        negProduct *= smallestNeg; 
        smallestNeg = i;
      } else {
        negProduct *= i;
      }
    } else {
      // i is strictly positive
      posProduct *= i;
    }

    //Recursive call here! 
    //Notice the index+1 for the index parameter which carries the progress 
    //in the array traversal
    return recursiveArrayTraversal(posProduct,negProduct,smallestNeg,index+1);
  }
}

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

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

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

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

线性版本

        List<Integer> vals = new ArrayList<>(List.of(5,-2,2,3,-4,-1));

        int prod = 0;
        int min = 1;
        for (int v : vals) {
            if (v == 0) {
                // ignore zero values
                continue;
            }
            if (prod == 0) {
                prod = 1;
            }
            prod *= v;
            // compute min to be the largest negative value in the list.
            if (v < 0 && min < Math.abs(v)) {
                min = v;
            }
        }
        if (prod < 0) {
            prod /= min;
        }

        System.out.println("Maximum product = " + prod);
    }

递归版本

        int prod = prod(vals,new int[] {0},vals.size());
        System.out.println("Maximum product = " + prod);

    public static int prod(List<Integer> vals,int[]min,int size) {
        int prod = 0;
        if(vals.size() > 0) {
            int t = vals.get(0);
             if (t < 0 && min[0] < Math.abs(t)) {
                    min[0] = t;
             }
             prod = prod(vals.subList(1,vals.size()),min,vals.size());
        }
        if (vals.isEmpty() || vals.get(0) == 0) {
            return prod;
        }

        if (prod == 0) {
           prod = 1;
        }
        prod *= t;

        if (vals.size() == size && prod < 0) {
            prod/=min[0];
        }
        return prod;    
    }

这是我的解决方案-保持打开状态以进行优化并确定运行时。这是一种通用解决方案，可在列表中查找整数的所有组合的乘积。当然，有一个O（n）解决方案，但我也介绍了此解决方案。

import java.util.ArrayList;
import java.util.List;

public class MaxProd {

    int[] input = {1,3};

    // int[] input = {-2,-1,3};

    public static void main(String[] args) {
        MaxProd m = new MaxProd();
        List<Integer> ll =  m.max(0);
        for (int i : ll) {
            System.out.println(i);
        }
        ll.sort((x,y) -> Integer.compare(x,y));
        System.out.println("The max: " + ll.get(ll.size() -1 ));

    }

    private List<Integer> max(int index) {
        if (index < input.length){
            List<Integer> l = new ArrayList<>();
            List<Integer> retList = max(index + 1);

            for (int j : retList){
                l.add(input[index] * j);
            }
            l.add(input[index]);
            l.addAll(retList);
            return l;
        }
        else return new ArrayList<>();

    }
}

它打印：

6
2
3
1
6
2
3
The max: 6

如果需求受到限制（如本例所示），则无需生成所有组合即可得出线性解，就可以通过。另外，我在最后排序。注意：您只需在返回列表中单次通过即可轻松获得结果，以找到其他答案中指定的最大乘积。

首先，始终在列表中找到0，将数组拆分为子问题：

 1 -2  4 -1  8  0  4  1  0 -3 -4  0  1  3 -5
|_____________|   |____|   |____|   |_______|
       p1           p2       p3         p4 

然后，对于每个问题pi，计算其中有多少个负数。

如果pi的负数是偶数（或根本没有负数），则pi的答案是其所有元素的乘积。

如果pi仅具有1个负数（例如n），则答案将是n右边的所有元素的乘积与所有元素的乘积之间的最大值n左侧的元素。

如果pi具有奇数个负数（仅大于1），请调用最左边的负数l的索引和最右边的负数r的索引。假设pi有n个元素，答案将是：

max(
    pi[  0  ] * pi[  1  ] * ... * pi[r - 1],pi[l + 1] * pi[l + 2] * ... * pi[  n  ]
)

认识到这一点，很容易为该问题的解决方案的每个步骤编写一个递归：在O（n）中将问题分为零的递归，另一个为负数的计数和另一个寻找答案的递归。