152. Maximum Product Subarray.md

152. Maximum Product Subarray

---

leetcode Daily Challenge on September 11th, 2020.

---

Difficulty : Medium

Related Topics : Array、Dynamic Programming

---

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.

---

Solution

• mine
  • Java
    • ``

---

• the most votes

• Runtime: 1 ms, faster than 95.19%, Memory Usage: 39.5 MB, less than 71.63% of Java online submissions

  // O(N)time
  // O(1)space
  public int maxProduct(int[] A) {
      int n = A.length, res = A[0], l = 0, r = 0;
      for (int i = 0; i < n; i++) {
          l =  (l == 0 ? 1 : l) * A[i];
          r =  (r == 0 ? 1 : r) * A[n - 1 - i];
          res = Math.max(res, Math.max(l, r));
      }
      return res;
  }
  

---

• leetcode Solution

• Runtime: 1 ms, faster than 95.19%, Memory Usage: 39.5 MB, less than 71.63% of Java online submissions

  // O(N)time
  // O(1)space
  public int maxProduct(int[] nums) {
      // dpmax[i] = Max(dpmax[i - 1] * nums[i], dpmin[i - 1] * nums[i], nums[i]);
      // dpmin[i] = Min(dpmax[i - 1] * nums[i], dpmin[i - 1] * nums[i], nums[i]);
      int max = nums[0], min = nums[0], res = nums[0];
      for(int i = 1; i < nums.length; i++){
          int ma = max, mi = min;
          max = Math.max(ma * nums[i], Math.max(mi * nums[i], nums[i]));
          min = Math.min(mi * nums[i], Math.min(ma * nums[i], nums[i]));
          res = Math.max(res, Math.max(min, max));
      }
      return res;
  }
  

---