[LeetCode 152] Maximum Product Subarray

Question

link

Find the contiguous subarray within an array (containing at least one number) which has the largest product.

For example, given the array [2,3,-2,4],
the contiguous subarray [2,3] has the largest product = 6.

            <div id="tags" class="btn btn-xs btn-warning">Show Tags</div>
            <span class="hide">
              
              <a class="btn btn-xs btn-primary" href="/tag/array/">Array</a>
              
              <a class="btn btn-xs btn-primary" href="/tag/dynamic-programming/">Dynamic Programming</a>
              
            </span>
          
        </div>

Analysis

This is a pretty difficult question. It’s hard to write bug-free solution if you have never practised before.

So the first idea that comes to me is the case of array element = 0. Why this case? cuz the maximum subarray MUST NOT CONTAIN 0 unless the input is like {-1, 0, -1}. So we could divide array from 0s and calculate max sum seperately. This idea is good, though a little difficult in coding. Read it here or here.

Solution

After a bit exploration, I found a must easier apporach, thanks to code ganker and Yu. The idea is to simply ALWAYS CALCULATE preMax and preMin by using MAX/MIN(Val1, Val2, Val3) method.

My Code

public class Solution {
    public int maxProduct(int[] A) {
        if (A == null || A.length == 0) {
            return 0;
        } else if (A.length == 1) {
            return A[0];
        }

        int preMax = A[0];
        int preMin = A[0];
        int max = A[0];

        for (int i = 1; i < A.length; i++) {
            int temp = preMin;
            preMin = Math.min(Math.min(preMin * A[i], preMax * A[i]), A[i]);
            preMax = Math.max(Math.max(temp * A[i], preMax * A[i]), A[i]);
            max = Math.max(max, preMax);
        }

        return max;
    }
}