首页 > 代码库 > LeetCode--Maximum Product Subarray
LeetCode--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.
class Solution
{
public:
int maxProduct(int A[], int n)
{
if(n==0)
return -1;
if(n==1)
return A[0];
int max = 0;
int min = 0;
int res = 0;
if(A[0]>0)
max = A[0];
else
min = A[0];
res = max;
int temp_max;
int temp_min;
for(int i=1; i<n; i++)
{
temp_max = max;
temp_min = min;
if(A[i] > 0)
{
max = (temp_max!=0)? (temp_max*A[i]):A[i];
min = temp_min*A[i];
}
else if(A[i] < 0)
{
min = (temp_max!=0) ? (temp_max*A[i]):A[i];
max = temp_min*A[i];
}
else
{
max = 0;
min = 0;
}
res = (max>res)? max:res;
}
return res;
}
};另一种方法：
class Solution
{
public:
int maxProduct(int A[], int n)
{
if(n==0)
return -1;
if(n==1)
return A[0];
int* max = new int[n];
int* min = new int[n];
for(int i=0; i<n; i++)
{
max[i] = 0;
min[i] = 0;
}
if(A[0]>0)
max[0] = A[0];
else
min[0] = A[0];
for(int i=1; i<n; i++)
{
if(A[i]>0)
{
if(max[i-1]!=0)
max[i] = max[i-1]*A[i];
else
max[i] = A[i];
min[i] = min[i-1]*A[i];
}
else if(A[i]<0)
{
max[i] = min[i-1]*A[i];
if(max[i-1]!=0)
min[i] = max[i-1]*A[i];
else
min[i] = A[i];
}
}
int res = max[0];
for(int i=0; i<n; i++)
{
if(max[i]>res)
res = max[i];
}
return res;
}
};LeetCode--Maximum Product Subarray
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。