O(n)时间解决的面试题：乘积最大子数组
浏览数：21 /
时间：2015年06月08日
leetcode 152
? ?
问题描述
? ?
给定一个数组，求最大的连续子数组乘积最大
? ?
分析问题
? ?
跟求和最大子数组类似，我们也可以用动态规划来解这道题，解题之前我们需要考虑是否存在溢出，在不存在溢出的情况下我们需要记录之前乘积的绝对值，这里因为有正负性，负负得正，所以我们需要记录之前乘积的最大值和最小值两个值
? ?
算法实现
? ?
int maxProduct(vector<int> &nums){
int n=nums.size();
if(n==0){
//这里也可以返回0，只是一个约定俗成
return 1;
}
int min_i=nums[0],max_i=nums[0],g_min=nums[0],g_max=nums[0];
for(int i=1;i<n;++i){
int tempMin=min(nums[i],min(nums[i]*min_i,nums[i]*max_i));
int tempMax=max(nums[i],max(nums[i]*max_i,nums[i]*min_i));
min_i=tempMin;
max_i=tempMax;
g_min=min(g_min,min_i);
g_max=max(g_max,max_i);
}
return g_max;
}
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
