Given an array of integers A and an integer m, determine the maximum product of m consecutive integers in the array

Let's solve the problem that the array contains 0：

.
.
.
int product = 1;
int maxProduct = Integer.MIN_VALUE;
if ( m < 1) return 0;
for(int i = 0, len = a.length; i < len; i++ ) {
    if (a[i] == 0) a[i] = 1; // solution
    if (i < m) {
        product *= a[i];
        maxProduct = product;
    } else {
        product = product * a[i] / a[i - m];
        maxProduct = maxProduct > product ? maxProduct : product;
    }
}
return maxProduct; 

But the array is a reference type, which will change the original array, so is there a better way? yes! we have :

.
.
.
int product = 1;
int maxProduct = Integer.MIN_VALUE;
if ( m < 1) return 0;
for(int i = 0, len = a.length; i < len; i++ ) {
    int spi = a[i] == 0 ? 1 : a[i];
    if (spi == 0) spi = 1;
    if (i < m) {
        product *= spi;
        maxProduct = product;
    } else {
        int spi_m = a[i - m] == 0 ? 1 : a[i - m];
        product = product * spi / spi_m;
        maxProduct = maxProduct > product ? maxProduct : product;
    }
}
return maxProduct; 

Here is the original answer：

.
.
.
int product = 1;
int maxProduct = Integer.MIN_VALUE;
if ( m < 1) return 0;
for(int i = 0, len = a.length; i < len; i++ ) {
    if (i < m) {
        product *= a[i];
        maxProduct = product;
    } else {
        product = product * a[i] / a[i - m];
        maxProduct = maxProduct > product ? maxProduct : product;
    }
}
return maxProduct;  

an array like this: 1,2,3,4,5,6,7,10,8,9

if m is 3

so, in for loop:

1. when i = 0, i = 1, i = 2 (i < 3 ) product *= a[i] => product = 1 * 1, product = 1 * 2 (now product is 2), product = 2 * 3 = 1 * 2 * 3 (m consecutive integers in the array)

maxProduct = 1, maxProduct = 2, maxProduct = 6

then i = 3,4,5,6,7,10,8,9 (i >= 3) if i is 3 product = product * a[i] / a[i - m] = 1 * 2 * 3 * 4 / 1 = 2 * 3 * 4(m consecutive integers in the array)

product > maxProduct

so the maxProduct now is product

if i is 4 product = product * a[i] / a[i - m] = 2 * 3 * 4 * 5 / 2 = 3 * 4 * 5(m consecutive integers in the array)

product > maxProduct

so the maxProduct now is product

but when i > 8

product < maxProduct

maxProduct will still maxProduct not change

!!! english is hard!

First off, there is no O(n+m). Since m <= n by definition, O(n+m) <= O(n+n) <= O(2n) and O(2n) is O(n). Secondly- the trick is that you don't need to loop to calculate the product every time. If for index (i, i+1, ... i+m-1) the product is p, then the product for (i+1, i+2..., i+m) is p/a[i]*a[i+m]. So you can calculate the new product by math rather than a second inner loop.

int product = initial_product(a,m); //gets the initial product
for(int i=m; i < a.length(); i++) {
    product = product * a[i]/a[i-m-1]
    //Check value of product here
}

Use a rolling product of m elements to find the max product in one pass.

Pseudo code:

1. multiply the first m numbers, saving as max and current
2. iterate over the remaining elements:
   1. set current to current divided by element i-m
   2. set current to current multiplied by element i
   3. set max to max(max, current)

This is a single pass over the array, so it's O(n).

In code:

public static int maxProduct(int[] a, int m) {
    int maxProduct = Integer.MIN_VALUE, current = 1;
    for (int i = 0; i < a.length; i++) {
        if (i < m) {
            current *= a[i];
        } else {
            current = current / a[i - m] * a[i]; // see note below
            maxProduct = Math.max(maxProduct, current);
        }
    }
    return maxProduct;
}

Integer division is safe (won't result in non-integer) because current has a[i-m] as a factor, current having been built from it.

An IntStream version

public static int maxProduct(int[] a, int m) {
    if (m <= 0) {
        throw new IllegalArgumentException();
    }
    m = Math.max(m, a.length);
    int product = IntStream.of(a).limit(m).sum();

   
    int maxProduct = product;
    for (int i = m; i < a.length; i++) {
        product /= a[i - m];
        product *= a[i];
        maxProduct = Math.max(maxProduct, product);
    }
    return maxProduct;
    
    /* MY BUG
    return IntStream.range(m, a.length)
        .iterate(product, i-> (pr -> (pr / a[i - m]) * a[i]))
        .max().orElse(0);
    */
}

A bit of APL feeling.

The time complexity is O(N). It is using a running product, deleting the contribution of the oldest factor and adding the new factor: 2 operations, O(1). Repeated N - m times, hence O(N).