LeetCode 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.

解析：计算子数组的最大乘积。这个题目类似于 leetcode 53 https://xianpengcui.com/2018/05/07/53-maximum-subarray/。53这个是求子数组的最大和。这个题目更复杂一些，这里是求最大乘积，涉及到0和负数，负数会使最大值变为最小值，最小值变为最大值。也是采用动态规划的思想，计算截止当前元素nums[i]的数值处理。 这道题目的妙处在于它不仅仅依赖了一个状态（前一个数所能获得的最大乘积），而是两个状态（最大和最小乘积）。所以这里使用了两个变量imax、imin分别记录到当前位置的最大值和最小值。这里不用数组dp的原因在于dp[i]只依赖于dp[i-1]。在处理到负数的时候，将max和min交换。

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int len = nums.size();
        int result = nums[0];
         //imax和imin分别记录截止当前位置的最大值和最小值
        for(int i=1, imax=result,imin=result; i < len; i++)
        {
            if(nums[i] < 0)//当前元素为负数，则交换imax和imin
                swap(imax, imin);
            imax = max(imax*nums[i], nums[i]);//当前元素是否选择乘以已有值还是单独选择
            imin = min(imin*nums[i], nums[i]);
            result = max(result, imax);//更新全局数值
        }
        return result;
    }
};

比起暴力求解，这种方法时间复杂度减少了很多。

参考：

https://leetcode.com/problems/maximum-product-subarray/discuss/48230/Possibly-simplest-solution-with-O(n)-time-complexity