用织梦做外文网站,wordpress icon设置,wordpress综合检测工具,天元建设集团有限公司在哪个区152. 乘积最大子数组
题目描述#xff1a;
给你一个整数数组nums#xff0c;请你找出数组中乘积最大的非空连续子数组#xff0c;并返回该子数组所对应的乘积
思路1#xff1a;贪心
由于 n u m s [ i ] nums[i] nums[i]都是整数#xff0c;所以多乘一些数肯定不会让绝…152. 乘积最大子数组
题目描述
给你一个整数数组nums请你找出数组中乘积最大的非空连续子数组并返回该子数组所对应的乘积
思路1贪心
由于 n u m s [ i ] nums[i] nums[i]都是整数所以多乘一些数肯定不会让绝对值变小所以我们就要尽可能多乘一些数
首先我们考虑最简单的例子也就是不包含0的情况
统计负数的数量如果是偶数那直接返回所有数的乘积即可如果负数的数量是奇数我们就考虑删掉一个负数由于我们上面说过多乘一些数不会让乘积的绝对值变小所以我们要尽可能少删数从左往右找到第一个下标为id1从右往左找到第一个下标为id2要么是删id1往左的所有数要么是删id2往右的所有数两种情况取最大值就行你可能会怀疑为什么答案不可能是被删除的那一段因为被删除的那一段都在另一半计算过了删id1往左的所有数时这段在计算删id2往右的所有数时被计算过了
class Solution {
public:int fuck(int l, int r, vectorintnums){if(l r || l 0 || r nums.size())return -2e9;if(l r)return nums[l];int mul 1;for(int i l; i r; i)mul * (nums[i] 0 ? 1 : -1);if(mul 0){for(int i l; i r; i)mul * nums[i];return mul;}mul -1;int id1 -1, id2 -1;for(int i l; i r; i){mul * (nums[i] 0 ? 1 : -1);if(mul 0){id1 i;break;}}int ans1 1, ans2 1;for(int i id1 1; i r; i){ans1 * nums[i];}mul -1;for(int i r; i l; --i){mul * (nums[i] 0 ? 1 : -1);if(mul 0){id2 i;break;}}for(int i id2 - 1; i l; --i){ans2 * nums[i];}return max(ans1, ans2);}int maxProduct(vectorint nums) {vectorintv;for(int i 0; i nums.size(); i){if(nums[i] 0)v.push_back(i);}if(v.empty())return fuck(0, nums.size() - 1, nums);int ans 0;v.push_back(nums.size());int pre -1;for(int i 0; i v.size(); i){ans max(ans, fuck(pre 1, v[i] - 1, nums));pre v[i];}return ans;}
};思路2:DP
这题和最大子数组和的题型有一点像但是不可以像它那样去进行转移不能仅仅维护一个最大值这样会忽略偶数个负数乘起来也是正数的情况有一种局部贪心的感觉
所以还需要维护一个最小值 状态 m a x n [ i ] maxn[i] maxn[i]表示以 n u m s [ i ] nums[i] nums[i]结尾的子数组乘积的最大值 m i n x [ i ] minx[i] minx[i]表示以 n u m s [ i ] nums[i] nums[i]结尾的子数组乘积的最小值 转移方程 n u m [ i ] 0 num[i] 0 num[i]0 m a x n [ i ] m a x ( n u m s [ i ] , m a x n [ i − 1 ] ∗ n u m s [ i ] ) ; maxn[i] max(nums[i], maxn[i - 1] * nums[i]); maxn[i]max(nums[i],maxn[i−1]∗nums[i]); m i n x [ i ] m i n ( m i n x [ i − 1 ] ∗ n u m s [ i ] , n u m s [ i ] ) ; minx[i] min(minx[i - 1] * nums[i], nums[i]); minx[i]min(minx[i−1]∗nums[i],nums[i]); n u m [ i ] 0 num[i] 0 num[i]0 m a x n [ i ] m a x ( m i n x [ i − 1 ] ∗ n u m s [ i ] , n u m s [ i ] ) ; maxn[i] max(minx[i - 1] * nums[i], nums[i]); maxn[i]max(minx[i−1]∗nums[i],nums[i]); m i n x [ i ] m i n ( m a x n [ i − 1 ] ∗ n u m s [ i ] , n u m s [ i ] ) ; minx[i] min(maxn[i - 1] * nums[i], nums[i]); minx[i]min(maxn[i−1]∗nums[i],nums[i]);
为了解决数据加强的问题可以用double卡过去
class Solution {
public:int maxProduct(vectorint nums) {int n nums.size();vectordoublemaxn(n), minx(n);double ans nums[0];maxn[0] minx[0] nums[0];for(int i 1; i n; i){if(nums[i] 0){maxn[i] max((double)nums[i], maxn[i - 1] * nums[i]);minx[i] min(minx[i - 1] * nums[i], (double)nums[i]);}else if(nums[i] 0){maxn[i] max(minx[i - 1] * nums[i], (double)nums[i]);minx[i] min(maxn[i - 1] * nums[i], (double)nums[i]);}ans max(ans, maxn[i]);}return (int)ans;}
};
