Skip to content

Latest commit

 

History

History
 
 

152.Maximum-Product-Subarray

152.Maximum-Product-Subarray

此题是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中的最大值。

Leetcode Link