先来个之前写过觉得还算值得练习的DP题目~152. Maximum Product Subarray,之前一时看了没有头绪该怎麽写,把经过过程写下来~
本来看到题目转过很多想法~ 想说都是整数,那只要结果是正的&不是0,都是越长越好,所以可能可以预设全部相乘,这个当暂存的最大值(greedy魂上身):如果是0或是负的再去检查;是负的就从两边找到第一个负的看哪边乘起来比较大就不要,变回原本问题,更新最大值之後继续找,就是从两边去削减,直到变成正的或是整条都没了;是0的就看从哪边去掉0比较不伤(直接比两边结果),但想不出来怎麽实现,所以看了别人的想法当提示,我现在也来当那个别人,说不定看到这个想法就可以解出来了~
max(前一个*该个,该个)、min(前一个*该个,该个)
,来进行更新。为什麽需要存最小值?因为如果下一个是负数的话就需要,大小值会整个反过来,就不用特别考虑什麽最大值、最小值、0要怎麽取了反正一定是3者之一,直觉易懂,程序码如下:class Solution {
public:
int maxProduct(vector<int>& nums) {
// DP way
vector<int> maxProd(nums.size());
vector<int> minProd(nums.size());
// initial the first one
maxProd[0] = nums[0];
minProd[0] = nums[0];
int ans=nums[0];
// iterate to compute from the previous one
for(int i=1; i<nums.size(); ++i){
maxProd[i] = max({maxProd[i-1]*nums[i],minProd[i-1]*nums[i],nums[i]});
minProd[i] = min({maxProd[i-1]*nums[i],minProd[i-1]*nums[i],nums[i]});
ans = max(ans, maxProd[i]);
}
return ans;
}
};
另外也有看到leetcode讨论区神人的简化写法,整理如下:
class Solution {
public:
int maxProduct(vector<int>& nums) {
int res = nums[0], mx = res, mn = res;
for (int i = 1; i < nums.size(); ++i) {
if (nums[i] < 0) swap(mx, mn);
mx = max(nums[i], mx * nums[i]);
mn = min(nums[i], mn * nums[i]);
res = max(res, mx);
}
return res;
}
};
class Solution {
public:
int maxProduct(vector<int>& nums) {
// greedy, the subarray would either start from left or right
// record the current maxima value
int ans=-10;
// record the current product
int prod=1;
// start from right
for(int i=0; i<nums.size();++i){
prod*=nums[i];
ans=max(ans, prod);
// if 0 appears, regarded as subproblem starting from the next element
prod = nums[i]==0?1:prod;
}
// start from left
prod = 1;
for(int i=nums.size()-1; i>=0;--i){
prod*=nums[i];
ans=max(ans, prod);
// if 0 appears, regarded as subproblem starting from the next element
prod = nums[i]==0?1:prod;
}
return ans;
}
};
另外一样也有讨论区的大神把两个简化写在一起~
int maxProduct(vector<int> A) {
int n = A.size(), res = A[0], l = 0, r = 0;
for (int i = 0; i < n; i++) {
l = (l ? l : 1) * A[i];
r = (r ? r : 1) * A[n - 1 - i];
res = max(res, max(l, r));
}
return res;
}
今日挑战的题目乍看单纯但其实蛮有趣的(也蛮麻烦XD)改天把他补上~
前言 当我们已经可以进入shioaji这个厨房,却发现用来烹饪的厨具都锁在架上,我们只能用一些简单的...
修正Bug日 [ ] 修正首页的排版问题 [ ] 修正书本细节页面的排版问题 [ ] 修正新增照片到...
结语 完成了连续一个月的铁人赛了!当初觉得每天发一篇应该不会太难,甚至还在开赛前屯了四篇,结果事...
首先很感谢it铁人赛给予我这个机会,让我做到平时连想不会想到的事。因为对於我而言,实在是没什麽能够说...
Tableau 优点 Tableau 是一种企业级的商业智能 (BI, Business Intel...