題目鏈接

152.乘積最大子數組

class Solution {public int maxProduct(int[] nums) {int[] dpMax = new int[nums.length]; //包括nums[i]的乘積最大值int[] dpMin = new int[nums.length]; //包括nums[i]的乘積最小值int res = nums[0];dpMax[0] = nums[0];dpMin[0] = nums[0];for (int i = 1; i < nums.length; i++) {if (nums[i] >= 0) {dpMax[i] = Math.max(dpMax[i - 1] * nums[i], nums[i]);dpMin[i] = Math.min(dpMin[i - 1] * nums[i], nums[i]);} else {dpMax[i] = Math.max(dpMin[i - 1] * nums[i], nums[i]);dpMin[i] = Math.min(dpMax[i - 1] * nums[i], nums[i]);}res = Math.max(res, dpMax[i]);}return res;}
}

小結：因為可能有負數出現，可能讓最小的變成最大的，需要額外記錄當前最小值。