152.Maximum-Product-Subarray

152. Maximum Product Subarray

题目地址

https://leetcode.com/problems/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.

代码

Approach #1 O(1) space, O(n) running time

class Solution {
  public int maxProduct(int[] nums) {
        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;
  }
}

Approach #2

public int maxProduct(int[] A) {
    int n = A.length;
    int res = A[0];
    int 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;
}