algorithm - 如何计算具有 N 个元素的数组的 M 个元素的最大乘积

Question

问题是 给定一个整数数组和一个长度 L，找到一个长度为 L 的子数组，使得所有整数的乘积最大。 例子: 输入:{4, 1, -7, -8, 9}, 3 输出:{-7,-8,9}

我写了一个非常粗糙且逻辑上有缺陷的代码，没有给出任何合理的输出。也许有人可以指出我正确的方向

public class ProductProblem {
/*
 * Given an array of integers and a length L, find a sub-array of length L such that the products of all integers are the biggest.
   Example:
   Input: {4, 1, -7, -8, 9}, 3
   Output: {-7,-8,9}
 */
    int a[];
    int l;
    int maxProduct;

    public int findProduct(int[] input, int len,int product){
        int[] output=new int[len];
        for (int i=0;i<input.length;i++){
            if(len>=1){
                System.out.println(product);
                System.out.println("input[i]="+input[i]);
                product= product*input[i];
                findProduct(input,len-1,product);
                System.out.println("len="+len);
            }
            else {
                return product;
            }
        }
        if (product>maxProduct){
            maxProduct=product;
        }
        return product;
    }


    public static void main(String[] args){
        ProductProblem pp=new ProductProblem();
        int[] a={1,3,-6,3,5};
        pp.a=a;
        int max=pp.findProduct(a,3,1);
        System.out.println(max);
    }
}

Answer 1

假设子集不一定连续，下面的算法可以在O(n*Log(n))时间内求解，其中n为数组长度。

关键的观察是对于某个 k 值，解决方案必须由前 2*k 个负数和前 L - 2*k 个正数组成。

1. 将正数按降序排列到数组P中
2. 将负数按绝对值降序排列到数组N中
3. 特殊情况:如果 P 为空且 L 为奇数(表示负结果)，则返回 N 尾部的 L 项。否则:
4. 计算P和N的累加积，分别存入P'和N'。也就是说，P'[i] = P[1] * P[2] * ... * P[i]。设 P'[0]=N'[0]=1。
5. 循环 k 从 0 到 L/2，并计算 P'[L-2*k] * N'[2*k]。最大结果对应于最佳子集，然后可以从 P 和 N 中再现。