152. Maximum Product Subarray

Given an integer array nums, find the contiguous subarray within an array (containing at least one number) which has the largest product.

Example 1:

Input: [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.

Example 2:

Input: [-2,0,-1]
Output: 0 

Explanation: The result cannot be 2, because [-2,-1] is not a subarray. 

My answer:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46

public class Solution { public int maxProduct(int[] A) { //Previous answer // if (A.length == 0) { // return 0; // } // int maxherepre = A[0]; // int minherepre = A[0]; // int maxsofar = A[0]; // int maxhere, minhere; // for (int i = 1; i < A.length; i++) { // maxhere = Math.max(Math.max(maxherepre * A[i], minherepre * A[i]), A[i]); // minhere = Math.min(Math.min(maxherepre * A[i], minherepre * A[i]), A[i]); // maxsofar = Math.max(maxhere, maxsofar); // maxherepre = maxhere; // minherepre = minhere; // } // return maxsofar; // current answer if (A.length == 0) { return 0; } if (A.length == 1) { return A[0]; } // dp[i][0] is the max value of product with ith elment included // dp[i][1] is the min value of product with ith elment included int[][] dp = new int[A.length][2]; dp[0][0] = A[0]; dp[0][1] = A[0]; for (int i = 1; i < A.length; i++) { // max product can only come from dp[i].min * A[i], dp[i].max * A[i], A[i] dp[i][0] = Math.max(A[i], Math.max(dp[i-1][0] * A[i], dp[i-1][1] * A[i])); dp[i][1] = Math.min(A[i], Math.min(dp[i-1][0] * A[i], dp[i-1][1] * A[i])); } int result = Integer.MIN_VALUE; for (int i = 0; i < dp.length; i ++) { result = Math.max(result, dp[i][0]); } return result; } }