0152. Maximum Product Subarray (M)

题目

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.

题意

在给定数组中找到一个子数组，使其积最大。

思路

动态规划。sm[i]表示以nums[i]为结尾的子数组能得到的最小乘积，lg[i]表示以nums[i]为结尾的子数组能得到的最大乘积。可以得到递推式：

代码实现

Java

class Solution {
    public int maxProduct(int[] nums) {
        int ans = nums[0];
        int[] sm = new int[nums.length];
        int[] lg = new int[nums.length];
        sm[0] = nums[0];
        lg[0] = nums[0];
        for (int i = 1; i < nums.length; i++) {
            sm[i] = Math.min(nums[i], Math.min(nums[i] * sm[i - 1], nums[i] * lg[i - 1]));
            lg[i] = Math.max(nums[i], Math.max(nums[i] * sm[i - 1], nums[i] * lg[i - 1]));
            ans = Math.max(ans, lg[i]);
        }
        return ans;
    }
}