Maximum Product Subarray

时间:2024-08-28 08:06:31

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;
}