[leetcode] 152. Maximum Product Subarray

[leetcode] 152. Maximum Product Subarray

Description

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: 6Explanation: [2,3] has the largest product 6.

Example 2:

Input: [-2,0,-1]Output: 0Explanation: The result cannot be 2, because [-2,-1] is not a subarray.

分析

题目的意思是：找到一个连续子数组，使得它们的乘积最大。

1）如果当前元素为正数，那么极大值只可能扩大，所以应该继续扩展当前subarray： 2）如果当前元素为负数，那么极大值可能会变小，所以不清楚应该继续扩展当前subarray还是新起一个subarray： 3）如果当前元素为0，那么包括一个0会使得极大值成为0，而按照操作规定，这里的极大值应该大于等于1，所以应该舍弃当前元素，新起一个subarray. 对于第2中情况，我们用两个数组分别记录遍历的极大值和极小值，因此最大值只可能从nums[i],mums[i]*dp_max[i-1],nums[i]*dp_min[i-1]中产生。想一想看是不是这个道理。

代码

class Solution {public: int maxProduct(vector& nums) { int result=nums[0]; vector dp_max(nums.size(),0); vector dp_min(nums.size(),0); dp_max[0]=dp_min[0]=nums[0]; for(int i=1;i

参考文献

​​[LeetCode] Maximum Product Subarray 求最大子数组乘积​​​​[LeetCode] Maximum Product Subarray的4种解法​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。