import java.lang.reflect.Array;
    import java.util.*;
    public class Part1 {
    public static int maxProduct(Array[] a, int m) {
    int maxProduct = Integer.MIN_VALUE;
    if (a.length < m) {
        return 0;
    }
    for (int i = 0; i <= a.length - m; i  ) {
        int product = 1;
        for (int j = i; j < m   i; j  ) {
            product = product * Arrays.asList(a).indexOf(j);
        }
        maxProduct = Math.max(maxProduct, product);
    }
    return maxProduct;  
}

} I am trying to find the max product of m consecutive integers in an array and I believe I have come up with a viable solution. However, I need my solution to have a worse-case runtime of O(N).

CodePudding user response：

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
}

CodePudding user response：

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