Maximum Product Subarray

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.

看到这道题，很明显的一套动态规划类型的题目，和最长升序子序列之类的十分类似，那么首先就是想递推公式。

思路①：

subarray[i][j]表示数组中从第 i 到第 j 位置的数字组成的子数组的乘积。因此我们有如下递推公式：

subarray[i][j] = subarray[i][j-1] * array[j]

很显然，这种做法需要一个二重循环，时间复杂度是O(n^2)

思路②：

因为考虑到，最大的一个子数组最大乘积可以分为两种情况：

A.之前的子数组乘积为负，当前的数字也为负，相乘为一个大正数

B.之前的子数组乘积为正，当前的数字也是正，相乘为一个正数

考虑到上面的两种情况，因此我们需要保存两个数组，分别记录当前的最大正整数乘积和最小负整数乘积

positive_subarray[i]:表示数组前i个数之前的最大相乘正值（包括第 i 个数）

negative_subarray[i]:表示数组前i个数之前的最大相乘负值（包括第 i 个数）

所以有：

当array[i] >= 0 时：

positive_subarray[i] = max( positive_subarray[i-1]*array[i], array[i] )

negative_subarray[i] = negative_subarray[i-1]*array[i]

当array[i] < 0 时：

positive_subarray[i] = negative_subarray[i-1]*array[i]

negative_subarray[i] = min( positive_subarray[i-1]*array[i], array[i])

这样程序的复杂度就降低到了O(n)

代码如下：

int  maxProduct(vector& nums)

{

　　if(nums.empty())

　　　　return 0;

　　vector positive_subarray = vector(nums.size(),0);

　　vector negative_subarray = vector(nums.size(),0);

　　int max_product;

　　int len = nums.size();

　　if(nums[0] < 0)

　　　　negative_subarray[0] = nums[0];

　　else

　　　　positive_subarray[0] = nums[0];

　　max_product = nums[0];

　　for(int i=1;i

　　{

　　　　if(nums[i]>=0)

　　　　{
　　　　　　positive_subarray[i] = max(positive_subarray[i-1]*nums[i],nums[i]);

　　　　　　negative_subarray[i] = negative_subarray[i-1]*nums[i];

　　　　}

　　　　else

　　　　{

　　　　　　positive_subarray[i] = negative_subarray[i-1]*nums[i];

　　　　　　negative_subarray[i] = min(positive_subarray[i-1]*nums[i],nums[i]);

　　　　}

　　　　if(positive_subarray[i]>max_product)

　　　　　　max_product = positive_subarray[i];

　　}

　　return max_product;

}

巴特西

Maximum Product Subarray

最新文章

热门文章