【Leetcode】152. Maximum Product S

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 解题步骤

1. 设计暴力算法，找到冗余
2. 设计并存储状态（一维，二维，三维数组，甚至Map）
3. 递归式（状态转移方程）
4. 自底向下计算最优解（编程方式）