152. 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.

链接： http://leetcode.com/problems/maximum-product-subarray/

6/13/2017

3ms, 57%

跟之前某道题有点像，但是忘记是哪道题了。思路是建立一个从左乘到右的数组，还有一个从右乘到左的数组。这两个数组都是如果碰到前一个是 0的话重新以当前数值开始乘。最后比较这两个数组当中的最大值。

space complexity O(n)

 1 public class Solution {
 2     public int maxProduct(int[] nums) {
 3         if (nums == null || nums.length == 0) {
 4             return 0;
 5         }
 6         if (nums.length == 1) {
 7             return nums[0];
 8         }
 9         
10         int[] fromLeft = new int[nums.length];
11         int[] fromRight = new int[nums.length];
12 
13         fromLeft[0] = nums[0];
14         for (int i = 1; i < nums.length; i++) {
15             if (fromLeft[i - 1] == 0) {
16                 fromLeft[i] = nums[i];
17             } else {
18                 fromLeft[i] = fromLeft[i - 1] * nums[i];
19             }
20         }
21         fromRight[nums.length - 1] = nums[nums.length - 1];
22         for (int i = nums.length - 2; i >= 0; i--) {
23             if (fromRight[i + 1] == 0) {
24                 fromRight[i] = nums[i];
25             } else {
26                 fromRight[i] = fromRight[i + 1] * nums[i];
27             }
28         }
29         int max = Math.max(fromLeft[0], fromRight[0]);
30         for (int i = 1; i < nums.length; i++) {
31             if (fromLeft[i] > max) {
32                 max = fromLeft[i];
33             }
34             if (fromRight[i] > max) {
35                 max = fromRight[i];
36             }
37         }
38         return max;
39     }
40 }

别人更好的做法，space complexity O(1), DP

https://discuss.leetcode.com/topic/4417/possibly-simplest-solution-with-o-n-time-complexity

http://www.cnblogs.com/yrbbest/p/4489668.html