152. 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.
求最大子数组的乘积是由最大子数组和演变而来，但是更复杂，求和的时候，遇到 0 不会改变最大值，遇到负数最大值减小。而求乘积的时候，遇到 0 会使得整个运算结果为 0，遇到负数，会使得最大乘积变成最小乘积。
这道题简单的办法就是用 DP 来做，维护两个 DP 数组，maxLocal[i] 存储 [0,i] 最大数组乘积，minLocal[i] 存储 [0,i] 最小数组乘积，初始化maxLocal[i] 和 minLocal[i] 为 nums[0]。
从这个数组的第二个数开始遍历，那么此时最大值和最小值都将从 maxLocal[i - 1] * nums[i]，minLocal[i] * nums[i]，和 nums[i] 产生。我们用 maxLocal[i] 和 minLocal[i] 更新最大和最小值，然后我们用 global 存储当前最大的乘积。
时间复杂度 O(n)
class Solution {
public int maxProduct(int[] arr) {
if (arr == null || arr.length == 0) {
return 0;
}
int maxLocal[] = new int[arr.length+1];
int minLocal[] = new int[arr.length+1];
maxLocal[0] = arr[0];
minLocal[0] = arr[0];
int global = maxLocal[0];
for(int i=1;i<arr.length;i++){
maxLocal[i] = Math.max(Math.max(arr[i]*maxLocal[i-1],arr[i]*minLocal[i-1]),arr[i]);
minLocal[i] = Math.min(Math.min(arr[i]*maxLocal[i-1],arr[i]*minLocal[i-1]),arr[i]);
global = Math.max(global,maxLocal[i]);
}
return global;
}
}
DP 解题步骤
- 设计暴力算法，找到冗余
- 设计并存储状态（一维，二维，三维数组，甚至Map）
- 递归式（状态转移方程）
- 自底向下计算最优解（编程方式）
