NC83. 连续子数组的最大乘积
描述
示例1
输入:
[3,2,-1,4]
输出:
6
说明:
子数组[3,2]的乘积为6，[3,2,-1,4]的乘积为-24，[4]的乘积为4，故返回6示例2
输入:
[-3,0,-2]
输出:
0
说明:
因为0在中间，所有包含0的子数组的乘积都为0，另外的数都是负数，所以最大乘积的子数组为[0]，返回为0，因为子数组要求是连续的，所以[-3,-2]不是[-3,0,-2]的子数组，所以不能为6，示例3
输入:
[-3,2,-2]
输出:
12
C++ 解法, 执行用时: 19ms, 内存消耗: 5044KB, 提交时间: 2022-02-24
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param nums int整型vector
* @return int整型
*/
int maxProduct(vector<int>& arr) {
int n = arr.size();
if (n == 0) {
return 0;
}
else if (n == 1) {
return arr[0];
}
int p = arr[0];
int maxP = arr[0];
int minP = arr[0];
for (int i = 1; i < n; i++) {
int t = maxP;
maxP = max(minP *arr[i], max(maxP * arr[i], arr[i]) );
minP = min(minP * arr[i], min(t * arr[i], arr[i]));
p = max(maxP, p);
}
return p;
}
};
C++ 解法, 执行用时: 19ms, 内存消耗: 5504KB, 提交时间: 2022-02-16
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param nums int整型vector
* @return int整型
*/
int maxProduct(vector<int>& nums) {
int size = nums.size();
if (size == 1) return nums[0];
int result = nums[0];
int maxDP[size]; // maxDP[i]表示以第i个值结尾的连续子数组的最大乘积
int minDP[size]; // minDP[i]表示以第i个值结尾的连续子数组的最小乘积
maxDP[0] = nums[0];
minDP[0] = nums[0];
for (int i = 1; i < size; i++)
{
// 因为以第i个值为结尾，所以nums[i]是必然被选择的
int tmpMax = max(nums[i], nums[i]*maxDP[i-1]);
maxDP[i] = max(tmpMax, nums[i]*minDP[i-1]);
int tmpMin = min(nums[i], nums[i]*maxDP[i-1]);
minDP[i] = min(tmpMin, nums[i]*minDP[i-1]);
result = max(result, maxDP[i]);
}
return result;
}
};
C++ 解法, 执行用时: 20ms, 内存消耗: 4908KB, 提交时间: 2022-02-13
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param nums int整型vector
* @return int整型
*/
int maxProduct(vector<int>& nums) {
// write code here
int res = nums[0];
vector<int> mi(nums.size());
mi[0] = nums[0];
vector<int> mx(nums.size());
mx[0] = nums[0];
for(int i=1;i<nums.size();i++)
{
if(nums[i]>0)
{
mx[i] = max(mx[i-1]*nums[i],nums[i]);
mi[i] = min(mi[i-1]*nums[i],nums[i]);
}
else
{
mx[i] = max(mi[i-1]*nums[i],nums[i]);
mi[i] = min(mx[i-1]*nums[i],nums[i]);
}
res = max(res,mx[i]);
}
return res;
}
};
C++ 解法, 执行用时: 20ms, 内存消耗: 4932KB, 提交时间: 2022-05-08
class Solution {
public:
int maxProduct(vector<int>& arr) {
int n = arr.size();
if (n == 0) {
return 0;
} else if (n == 1) {
return arr[0];
}
int p = arr[0];
int maxP = arr[0];
int minP = arr[0];
for (int i = 1; i < n; i++) {
int t = maxP;
maxP = max(minP * arr[i], max(maxP * arr[i], arr[i]) );
minP = min(minP * arr[i], min(t * arr[i], arr[i]));
p = max(maxP, p);
}
return p;
}
};
C++ 解法, 执行用时: 20ms, 内存消耗: 5564KB, 提交时间: 2022-07-27
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
* @param nums int整型vector
* @return int整型
*/
int maxProduct(vector<int>& nums) {
//vector<int> pos(nums); // 存储以nums[i] 结尾的最大乘积
int pos[2] = {nums[0], INT_MIN};
//vector<int> neg(nums); // 存储以 nums[i] 结尾的最小乘积
int neg[2] = {nums[0], INT_MAX};
int result = nums[0];
for (int i = 1; i < nums.size(); i++) {
pos[i % 2] = max(nums[i], max(nums[i] * pos[(i + 1) % 2],
nums[i] * neg[(i + 1) % 2]));
neg[i % 2] = min(nums[i], min(nums[i] * pos[(i + 1) % 2],
nums[i] * neg[(i + 1) % 2]));
result = max(result, pos[i % 2]);
}
return result;
}
};