Question

link

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;
    }
}