152. Maximum Product Subarray

Source link: https://leetcode.com/problems/maximum-product-subarray/

Design

There are three kinds of situations: positive * positive, negative * positive and negative * negative, so we should store both accumulated maximum and minimum values of previous elements. The reason why we need to store the minimum accumulated values is because there might be negative for the current value, and the smaller the previous accumulated negative values, the bigger the product result.

  1. Initialize three variables, one for storing the final result, both of others storing maximum and minimum accumulated values.
  2. Compare the current value times previous accumulated values with the current value.
  3. Return the maximum value.

Implementation

class Solution {
  public int maxProduct(int[] nums) {
    if (nums == null || nums.length == 0) return -1;
    int res = nums[0];
    int max = nums[0];
    int min = nums[0];
    for (int i = 1; i < nums.length; i++) {
      int temp = max;
      max = Math.max(Math.max(max * nums[i], min * nums[i]), nums[i]);
      min = Math.min(Math.min(min * nums[i], temp * nums[i]), nums[i]);

      res = Math.max(res, max);
    }
    return res;
  }
}

Complexity Analysis

Time: $O(n)$

Space: $O(1)$