How to calculate maximum product of M elements of an array with N elements

Question

The question is 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}

I wrote a very crude and logically flawed code which does not give any reasonable output. Perhaps someone can point me in the right direction

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

According to the original question source, we are looking for a subarray (substring), which must be contiguous.

To quickly add numbers to a multiset and get the product of the multiset, we can use the data structure of (product of nonzero numbers, number of zeros). This structure takes O(1) space and allows us to do 3 operations (add value, remove value, get product) in O(1) time, assuming numbers are limited to a machine word size, with O(1) multiplication and division time for those words, as supporting arbitrarily large numbers needs higher complexity.

We can create this structure, add L items, and then remove and add one item each iteration to check all other subarrays. This will take O(N) time and O(1) auxiliary space for an input array of length N.

We can also return all possible starting indices to represent all the solutions when there are multiple. This requires O(N-L) space to return the indices.

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))

Output:

[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])

---

If we were instead looking for an unordered subsequence (subset but with multisets), we can use this O(N) time solution, which also returns the elements:

1. If the array length is L, return the array.
2. If L is odd and there are no positive values, use introselect to partition the array at index L, using (value) => -value as the key function for an ascending sort to get the maximum L values, and return them. This takes O(N) time.
3. Use introselect to partition the array at index L, using (value) => -abs(value) as the key function for an ascending sort. Let's call the first L items big and the rest small.
4. Multiply the items in big. If the result is not negative, return big.
5. There are two possible swaps that will fix the sign, so check both and return the one with the bigger product:
   1. Swap the maximum value in small (biggest positive) with the maximum negative value in big (smallest negative)
   2. Swap the minimum value in small (biggest negative) with the minimum positive value in big (smallest positive)

Answer 2

Assuming that the subset is not necessarily contiguous, the following algorithm can solve it in O(n*Log(n)) time, where n is the array length.

The key observation is that the solution must be composed of the top 2*k negative numbers, and the top L - 2*k positive numbers, for some value of k.

1. Sort the positive numbers into array P, in descending order
2. Sort the negative numbers into array N, in descending absolute value order
3. Special case: if P is empty and L is odd (meaning a negative result), return the L items from N's tail. Otherwise:
4. Compute the cumulative product of P and N, and store in P' and N' respectively. That is, P'[i] = P[1] * P[2] * ... * P[i]. set P'[0]=N'[0]=1.
5. Loop on k from 0 to L/2, and calculate P'[L-2*k] * N'[2*k]. The maximum result corresponds to the best subset, which can then be reproduced from P and N.

Answer 3

Most languages allow you to sort by array value (or key value) and then you can slice the array to the top N elements.

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

Answer 4

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;
}

The principle here is that the product of each consecutive subarray of length L (L specified as the method parameter) is recorded, with the maximum product stored in a variable. At the end of the function, the maximum product subarray is re-created and returned.

You can find the set of non-contiguous subarrays as follows (and then find max product in a similar fashion):

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);
    }
}