152. Maximum Product Subarray

• 152. Maximum Product Subarray
  • Description
  • Intuition
  • Pitfall
  • Solution

Description

Here

Intuition

解出来不难，也没啥坑，比较intuitive的解法是

 public int maxProduct(int[] nums) {
    if (nums == null || nums.length == 0) {
      return 0;
    }
    int maxEndHerePos = Math.max(nums[0], 0), maxSoFarPos = nums[0],
        minEndHereNeg = Math.min(nums[0], 0);
    for (int i = 1; i < nums.length; ++i) {
      final int prevMaxEndHerePos = maxEndHerePos,
          prevMinEndHereNeg = minEndHereNeg;
      if (nums[i] == 0) {
        maxEndHerePos = 0;
        minEndHereNeg = 0;
      } else if (nums[i] < 0) {
        maxEndHerePos = prevMinEndHereNeg * nums[i];
        minEndHereNeg = Math.min(prevMaxEndHerePos * nums[i], nums[i]);
      } else {
        maxEndHerePos = Math.max(nums[i], prevMaxEndHerePos * nums[i]);
        minEndHereNeg = prevMinEndHereNeg * nums[i];
      }
      maxSoFarPos = Math.max(maxSoFarPos, maxEndHerePos);
    }
    return maxSoFarPos;
  }

但其实可以用 maxSoFar, minEndHere, maxEndHere

  public int maxProduct(int[] nums) {
    int maxSoFar = nums[0];
    int maxHere = nums[0];
    int minHere = nums[0];

    for (int i = 1; i < nums.length; i++) {
      int preMax = maxHere; // backup
      maxHere = Math.max(Math.max(maxHere * nums[i], minHere * nums[i]), nums[i]);
      minHere = Math.min(Math.min(preMax * nums[i], minHere * nums[i]), nums[i]);
      maxSoFar = Math.max(maxSoFar, maxHere);
    }
    return maxSoFar;
  }

Pitfall

Solution

Solution