Print Largest product sub-array of size k

Share

Problem: For a given array of positive non-zero integers, find sub-array of size k with largest product.

Problem Explanation: For a given array a ={1, 2, 8, 10, 1, 3} and sub-array size 3,  the maximum product of sub-array of size 3 is 160.

Java Implementation

public int maxProductSubArray(int[] arr, int k) {
    int maxProduct = 1, prevProduct = maxProduct;

    for (int i = 0; i < k; i++) {
        prevProduct *= arr[i];
    }
    maxProduct = prevProduct;

    for (int i = 1; i <= arr.length - k; i++) {
        int curProduct = (prevProduct / arr[i - 1]) * arr[i + k - 1];
        if (curProduct > maxProduct) {
            maxProduct = curProduct;
        }
        prevProduct = curProduct;
    }

    return maxProduct;
}

TimeComplexity: O(n)

Note: If you find any other better way to approach to this problem or you find any issue/error in above code snippets/approaches – please share it in the comments section below and get a chance to enrol free of cost for an online Live Data Structure and Algorithm course (specially designed for interview preparation for software companies like Amazon, Google, Facebook, FlipKart, SnapDeal, HealthKart…)