如何计算具有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);
    }
}

- user3386479

---

你的意思是子数组指连续的子数组吗？ - pkacprzak

哦，糟糕，我没有考虑到那个。我一直以为它不是连续的。 - user3386479

问题的来源是这个：http://www.careercup.com/question?id=5752271719628800 - user3386479

Answer 1

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

关键观察是解决方案必须由前2*k个负数和前L-2*k个正数组成，其中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.从0到L/2循环k，并计算P'[L-2*k] * N'[2*k]。最大值对应于最佳子集，然后可以从P和N中重现它。

- Eyal Schneider

---

如果输入的所有元素都是零，循环将越界。 - Victor

这个答案与你的类似，但它声称在O(n)时间内运行。https://stackoverflow.com/a/42153733 - Victor

@Victor：这两个问题略有不同。在这里，我们需要最佳集合，而在另一个问题中，我们需要最大乘积本身。我怀疑这里的问题没有简单的线性解决方案，因为这将用比已知解决方案更简单的线性时间解决中位数问题（或任何顺序统计） 。 - Eyal Schneider

该链接回答声称使用introselect来在排名k处分割绝对值。 - Victor

这个问题确实有一个线性解决方案，因为 introselect 允许您通过对数组进行分区来解决第 k 小的统计量，使得第 k 项处于其排序位置，所有较小的值在它之前，所有较大的值在它之后，在线性时间内完成。 - Victor

Answer 2

public int[] findProduct(int[] integers, int L) {
    int maxProduct = Integer.MIN_VALUE;
    int start = 0;
    for (int i = 0; i + L < integers.length; i++) {
        int tmp = 1;
        for (int j = i; j < i + L; j++) tmp *= array[j];
        if (tmp > maxProduct) {
            maxProduct = tmp;
            start = i;
        }
    }
    int[] retVal = new int[L];
    for (int i = start; i < start + L; i++) retVal[i - start] = integers[i];
    return retVal;
}

这里的原则是记录长度为L（L作为方法参数指定）的每个连续子数组的乘积，并将最大乘积存储在一个变量中。在函数结束时，重新创建并返回最大乘积子数组。

您可以按以下方式找到非连续子数组集合（然后以类似的方式找到最大乘积）：

int[] subarrayL = new int[L];

public int[] findSubarrays(int[] integers, int L) {
    for (int i = 0; i < L; i++) {
        setSubarray(i, L);
    }
}

public void setSubarray(int[] integers, int i, int L) {
    for (int j = i; j < Math.min(integers.length, integers.length - L + i + 1); j++) {
        subarrayL[i] = integers[j];
        if (i + 1 < L) setSubarray(integers, i + 1, L);
    }
}

- La-comadreja

---

这种暴力解决方案虽然可行，但对于大规模输入来说效率低下。 - Victor

Answer 3

如果子数组应该是连续的，那么我们可以在O（N）时间内获得结果子数组。 以下是代码：

public int[] findProduct(int[] input, int L) {

    if( L < input.length || L == 0 ) {
        //invalid case
        return 0;
    }

    int max_product = -2e9;
    int result_start = 0;
    int temp_result = 1;

    for(int i = 0; i < L - 1; i++) {
        temp_result *= input[i];
    }

    int left = 0;

    for (int right = L - 1; right < input.length; right++) {
        temp_result *= input[right];
        if (temp_result > max_product) {
            max_product = temp_result;
            result_start = left;
        }

        temp_result /= input[left]; // removing the leftmost item as that will not be included in next sub array.

        left ++;
    }

    int[] sub_array = new int[L];
    for (int i = 0; i < L; i++) sub_array[i] = integers[result_start + i];
    return sub_array;
}

- Fallen

---

除了实际的代码之外，给出算法的高级描述/思路/伪代码总是一个好主意。 - Bernhard Barker

Answer 4

大多数编程语言都允许您按数组值（或键值）进行排序，然后您可以将数组切片到前N个元素。

var array = sort(array)
var length = 10
var biggest = array_slice(array, 0, length);

- Xeoncross

---

如果数组是 1, 2, -10, -200，而且 K = 2 呢？ - Fallen

Answer 5

根据原始问题来源，我们正在寻找一个连续的子数组（子串）。

为了快速向多重集合中添加数字并获取多重集合的乘积，我们可以使用数据结构（非零数的乘积，零的数量）。这个结构占用O(1)的空间，并且允许我们在O(1)的时间内进行3个操作（添加值，删除值，获取乘积），假设数字限制在机器字大小范围内，对于这些字来说，乘法和除法的时间复杂度为O(1)，因为支持任意大的数字需要更高的复杂度。

我们可以创建这个结构，添加L个项目，然后每次迭代删除和添加一个项目来检查所有其他子数组。对于长度为N的输入数组，这将花费O(N)的时间和O(1)的辅助空间。

当存在多个解时，我们还可以返回所有可能的起始索引来表示所有解决方案。这需要O(N-L)的空间来返回索引。

class QuickProduct:
    product = 1
    num_zero = 0

    def add(self, value):
        if value:
            self.product *= value
        else:
            self.num_zero += 1

    def remove(self, value):
        if value:
            self.product //= value
        else:
            self.num_zero -= 1

    def get_product(self):
        return 0 if self.num_zero else self.product

def highest_product_num(data, L):
    if len(data) < L:
        raise ValueError('L must not be smaller than length of data')

    q = QuickProduct()

    # add first L items
    for i in range(L):
        q.add(data[i])

    best = q.get_product()
    start_index = [0]

    # try all other possible subarrays
    for i in range(L, len(data)):
        q.remove(data[i - L])
        q.add(data[i])

        p = q.get_product()
        if best < p:
            best = p
            start_index = [i - L + 1]
        elif best == p:
            start_index.append(i - L + 1)

    return best, start_index

test_input = [
    ([4,1,-7,-8,9], 3),
    ([4,1,-7,-8,9,0,-8,-7,9,-8,-7,9,8,7,8], 3),
    ([1,3,-6,3,5], 3),
    ([1,2,3,4,5,6,7,8], 4), ([1,-2,3,4,5,100,2,3,1], 4),
    ([-10,-10,1,3,2], 4), ([1000,7,-6,2,2],4),
    ([-1, 0, 1], 2), ([2, 5, 8, 9, 1, 3, 7], 4),
    ([-1, -1, 2, 1], 2), ([-1000, -1, 2, 3], 2),
    ([3, 5, 2, 8, 3], 2), ([-1000, -1, 2, 3, 4, 5, 6, 7], 2)
]

for data, L in test_input:
    print(data, L, highest_product_num(data, L))

输出：

[4, 1, -7, -8, 9] 3 (504, [2])
[4, 1, -7, -8, 9, 0, -8, -7, 9, -8, -7, 9, 8, 7, 8] 3 (504, [2, 6, 7, 8, 9, 11])
[1, 3, -6, 3, 5] 3 (-18, [0])
[1, 2, 3, 4, 5, 6, 7, 8] 4 (1680, [4])
[1, -2, 3, 4, 5, 100, 2, 3, 1] 4 (6000, [2])
[-10, -10, 1, 3, 2] 4 (300, [0])
[1000, 7, -6, 2, 2] 4 (-168, [1])
[-1, 0, 1] 2 (0, [0, 1])
[2, 5, 8, 9, 1, 3, 7] 4 (720, [0])
[-1, -1, 2, 1] 2 (2, [2])
[-1000, -1, 2, 3] 2 (1000, [0])
[3, 5, 2, 8, 3] 2 (24, [3])
[-1000, -1, 2, 3, 4, 5, 6, 7] 2 (1000, [0])

---

如果我们要寻找的是一个无序子序列（子集但包含重复元素），我们可以使用这个O(N)时间复杂度的解决方案，它还会返回元素。

如果数组长度为L，则返回该数组。 如果L为奇数且没有正值，则使用introselect在索引L处对数组进行分区，使用(value) => -value作为键函数进行升序排序以获取最大的L个值，并返回它们。这需要O(N)时间。 使用introselect在索引L处对数组进行分区，使用(value) => -abs(value)作为键函数进行升序排序。将前L个项称为big，其余项称为small。 将big中的项相乘。如果结果不是负数，则返回big。 有两种可能的交换方式可以修复符号，因此检查两种方式并返回具有更大乘积的那一种： 1. 将small中的最大值（最大正数）与big中的最小负值（最小负数）进行交换 2. 将small中的最小值（最大负数）与big中的最小正值（最小正数）进行交换

- Victor