LeetCode/Dynamic_Programming/152.Maximum-Product-Subarray at master · wisdompeak/LeetCode · GitHub

Name		Name	Last commit message	Last commit date
parent directory ..
152.Maximum-Product-Subarray_DP.cpp		152.Maximum-Product-Subarray_DP.cpp
Readme.md		Readme.md

Readme.md

此题是053.Maximum-Subarray的进阶版。本题的关键点在于，如果nums[i]是负数，那么求以i为结尾的最大乘积子数组，其实转化为求以i-1为结尾的最小乘积子数组。所以我们每次考察以i为结尾的子数组时，需要同时保留最大和最小值。于是状态转移方程：

            curMax = max(max(preMin*nums[i],preMax*nums[i]),nums[i]);
            curMin = min(min(preMin*nums[i],preMax*nums[i]),nums[i]);

最后返回的结果不是最后的curMax,而是遍历每个回合的curMax中的最大值。