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

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

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