3

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);
    }
}
Improve this question
3
  • 1
    By subarray you mean a contiguous subarray? Commented Feb 28, 2014 at 20:00
  • oh shoot i didn't think of that. i was assuming that it is not contiguous Commented Feb 28, 2014 at 20:12
  • the source of the question is this careercup.com/question?id=5752271719628800 Commented Feb 28, 2014 at 20:13

4 Answers 4

Reset to default
5

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.
Improve this answer
Sign up to request clarification or add additional context in comments.

5 Comments

The loop would go out of bounds if all elements of the input are zero.
This answer is similar to yours, but it claims to run in O(n) time. stackoverflow.com/a/42153733
@Victor: The questions are slightly different. Here we need the best set, and in the other question we need the max product itself. I doubt the question here has a simple linear solution, simply because this would have solved the median problem (or any order statistics) with a linear time solution which is simpler than the known one.
The linked answer claims to use introselect to partition absolute values at rank k.
This question does have a linear solution, since introselect allows you to solve the kth order statistic by partitioning the array such that item k is in its sorted position, and all smaller values are before it, and all larger values are after it, in linear time.
1 
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);
    }
}
Improve this answer

1 Comment

This brute-force solution works but is inefficient for large inputs.
0

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);
Improve this answer

1 Comment

What about for an array like, 1, 2, -10, -200 while K = 2 ?
0

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)
Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.