Range of maximum product subarray (Kadane algorithm variant)

Question

I have been trying to get the range of a Maximum Product of a subarray (studying for job interviews).

This has been already asked here (but no valid answers have been provided). Getting range of max product subarray using Kadanes algorithm

The trick/algorithm is explained well here: http://www.geeksforgeeks.org/maximum-product-subarray/

I am able to get the maximum product easily, but after a lot of tries, still can't figure out how to get the range (left and right indexes properly). Can anyone please help??

I have pasted my code, so you can just copy and run it quickly..

import java.util.*;

public class ArrayMax {

// maximum product
public static int[] getMaxProduct(int[] list)
{
    int max = 1, min = 1, maxProd = 0;
    int l = 0, left = 0, right = 0;

    for (int i = 0; i < list.length; i++) {

        // positive number!
        if (list[i] > 0) {
            max = max * list[i];
            min = Math.min(1, min * list[i]);
        }
        else if (list[i] == 0) {
            max = 1;    // reset all
            min = 1;
            l = i + 1;
        }
        else {
            // hold the current Max                                  
            int tempMax = max;
                     // need to update left here (but how??)
            max = Math.max(min * list[i], 1); // [-33, 3]
            min = tempMax * list[i];  // update min with prev max

        }

    //  System.out.printf("[%d %d]%n", max, min);       
        if (max >= maxProd) {
            maxProd = max;
            right = i;
            left = l;
        }
    }

    System.out.println("Max: " + maxProd);
    // copy array
    return Arrays.copyOfRange(list, left, right + 1);
}


// prints array
public static void printArray(int[] list) {

    System.out.print("[");
    for (int i = 0; i < list.length; i++) {     
        String sep = (i < list.length - 1) ? "," : "";
        System.out.printf("%d%s", list[i], sep);
    }

    System.out.print("]");
}

public static void main(String[] args) {

    int[][] list = {
        {5, 1, -3, -8},
        {0, 0, -11, -2, -3, 5},
        {2, 1, -2, 9}
    };

    for (int i = 0; i < list.length; i++) {
        int[] res = getMaxProduct(list[i]);

        printArray(list[i]);
        System.out.print(" => ");
        printArray(res);

        System.out.println();
    }
}
} 

Here are sample outputs:

Max: 120
[5,1,-3,-8] => [5,1,-3,-8]
Max: 30
[0,0,-11,-2,-3,5] => [-11,-2,-3,5]
Max: 9
[2,1,-2,9] => [2,1,-2,9]

As you can see, I am getting the maximum product, but the range is wrong.

Case#2, Max is 30 (correct answer: [-2,-3,5], showing: [-11,-2,-3,5])
Case#3, Max is 9 (correct answer: [9], giving: [2,1,-2,9])

Please help.

Answer 1

Easier way is to try to find left position/marker when you have calculated the maxProd (at the end). Your right position is accurate, so set left to right and divide maxProd by list[left] until you hit 1, while decrementing left. Thats when you have reached left.

The following code before the return should solve it.

int temp = maxProd;
left = right;
while (temp != 1) {
   temp = temp / list[left--];
}
left++;
// copy array
return Arrays.copyOfRange(list, left, right + 1);

Answer 2

I think you need to keep track of 2 values for l. One will represent the start index for the subarray of numbers that multiply to make max, while the other will represent the start index for the subarray of numbers that multiply to make min.

However, an even easier way is to simply wait until you have found the maximum answer (in maxProd) and its position (in right). At this point you can then loop over the array multiplying the elements of the list until your total reaches maxProd (starting at right and iterating backwards). The last element you multiplied must be the start of the subarray.