首页 > 代码库 > Maximum Product Subarray Leetcode
Maximum Product Subarray Leetcode
Find the contiguous subarray within an array (containing at least one number) which has the largest product.
For example, given the array [2,3,-2,4]
,
the contiguous subarray [2,3]
has the largest product = 6
.
这道题和Maximum Sum Subarray类似,也是考虑什么时候可以取得最大值。sum的话一遇到负数就可以重新考虑,product的话负数*负数可能是最大值,所以要保留局部最大值和局部最小值。
每次考虑最大值的时候,在:
前面的最大值乘这个数本身(这个数是正数),
这个数本身(这个数是负数或者这个数前面的数是负数,这个数本身是正数),
最小值乘这个数(最小值和这个数都是负数),
这三个里面选局部最大值。
每次考虑最小值的时候,在:
前面的最小值乘这个数本身(这个数是正数),
这个书本身(这个数是负数,前面的最小值也是负数),
最大值乘这个数(最大值是正数,这个数是负数),
这三个里面选局部最小值。
public class Solution { public int maxProduct(int[] nums) { if (nums == null || nums.length == 0) { return 0; } int[] curMax = new int[nums.length]; int[] curMin = new int[nums.length]; int res = nums[0]; curMax[0] = nums[0]; curMin[0] = nums[0]; for (int i = 1; i < nums.length; i++) { curMax[i] = Math.max(Math.max(curMax[i - 1] * nums[i], nums[i]), curMin[i - 1] * nums[i]); curMin[i] = Math.min(Math.min(curMax[i - 1] * nums[i], nums[i]), curMin[i - 1] * nums[i]); if (curMax[i] > res) { res = curMax[i]; } } return res; } }
改良了一下,可以用O(1) space,但是思路是一样的
public class Solution { public int maxProduct(int[] nums) { if (nums == null || nums.length == 0) { return 0; } int res = nums[0]; int curMax = nums[0]; int curMin = nums[0]; int max, min; for (int i = 1; i < nums.length; i++) { max = Math.max(Math.max(curMax * nums[i], nums[i]), curMin * nums[i]); min = Math.min(Math.min(curMax * nums[i], nums[i]), curMin * nums[i]); if (max > res) { res = max; } curMax = max; curMin = min; } return res; } }
这个动态规划做的不顺利,以后回顾一下吧。
Maximum Product Subarray Leetcode
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。