题解 | #连续子数组的最大乘积#
连续子数组的最大乘积
http://www.nowcoder.com/practice/abbec6a3779940aab2cc564b22d36859
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param nums int整型vector
* @return int整型
*/
int maxProduct(vector<int>& nums) {
// write code here
int n = nums.size();
vector<int> dp_pos(n, 0);
vector<int> dp_neg(n, 0);
dp_pos[0] = nums[0];
dp_neg[0] = nums[0];
int res = nums[0];
for(int i=1; i<n; i++){
dp_pos[i] = max(dp_pos[i-1]*nums[i], nums[i]);
dp_pos[i] = max(dp_neg[i-1]*nums[i], dp_pos[i]);
dp_neg[i] = min(dp_neg[i-1]*nums[i], nums[i]);
dp_neg[i] = min(dp_pos[i-1]*nums[i], dp_neg[i]);
res = max(res, dp_pos[i]);
}
return res;
}
};
查看1道真题和解析