Leetcode 题目解析之 Maximum Product Subarray
原创Leetcode 题目解析之 Maximum Product Subarray
原创
ruochen
发布于 2022-01-09 11:37:00
发布于 2022-01-09 11:37:00
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.
LeetCode第53题Maximum Subarray是求连续和最大的子数组，本题是求连续乘积最大的子数组。
在解法上是一样的，只是在求和时，是负就舍弃。但是在乘积中，因为负数*负数=正数，所以连续乘积为负数时，并不能舍弃这个数，因为如果数组的元素是负数，它可能成为乘积最大的数。
所以LeetCode第53题Maximum Subarray，只需要定义一个变量，用来记录和；本题要定义两个变量：positive和negative，分别记录当前乘积最大值和最小值。
public int maxProduct(int[] nums) {
int max = nums[0];
int positive = nums[0];
int negative = nums[0];
for (int i = 1; i < nums.length; i++) {
positive *= nums[i];
negative *= nums[i];
if (positive < negative) {
int t = positive;
positive = negative;
negative = t;
}
positive = Math.max(positive, nums[i]);
negative = Math.min(negative, nums[i]);
max = Math.max(max, positive);
}
return max;
}原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
评论
登录后参与评论
推荐阅读