[Leetcode] Maximum Product Subarray

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.

Solution 1:(Brute-Force approach)
s[i][j] represents the product of A.subarray(i,j). Initialize s, and update the value of max product each time. Then, after proceeding the nested for loop, return the max product.
However, this solution is Time Limit Exceeded
Time Complexity: O(n * n)
Space Complexity: O(n * n)
------------------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 length = A.length;
        int [][] s = new int[length][length];
        int maxProduct = Integer.MIN_VALUE;
     
        for (int i = 0; i < length; i++) {
            for (int j = 0; j < length; j++) {
                if (i >= j)
                    ;
                else if (i == j - 1)
                    s[i][j] = A[i] * A[j];
                else
                    s[i][j] = s[i][j - 1] * A[j];
                 
                if (maxProduct < s[i][j])
                    maxProduct = s[i][j];
            }
        }
     
        return maxProduct;
    }
}
------------------code------------------
Solution 2:
sMin[i] The min product subarray end with the index i.
sMax[i] The max product subarray end with the index i.
sMin[i] = The minimum of the three values: sMin[i - 1] * A[i], sMax[i - 1] * A[i], A[i]
sMin[i] = The maximum of the three values: sMin[i - 1] * A[i], sMax[i - 1] * A[i], A[i]

Accepted

Time Complexity: O(n)

Space Complexity: O(n)

------------------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 length = A.length;
        int [] sMax = new int[length];
        int [] sMin = new int[length];
        int maxProduct = A[0];
     
        sMax[0] = A[0];
        sMin[0] = A[0];
        for (int i = 1; i < length; i++) {
            sMax[i] = Math.max(Math.max(sMax[i - 1] * A[i], sMin[i - 1] * A[i]), A[i]);
            sMin[i] = Math.min(Math.min(sMax[i - 1] * A[i], sMin[i - 1] * A[i]), A[i]);
            maxProduct = Math.max(maxProduct, sMax[i]);
        }
     
        return maxProduct;
    }
}
------------------code------------------
There is also a O(n) solution that take O(1) space. See URL:
https://oj.leetcode.com/discuss/11923/sharing-my-solution-o-1-space-o-n-running-time