无锡公共建设中心网站,有了域名自己电脑怎么做网站,济源做网站的公司,个人养老金保险152. 乘积最大子数组 - 力扣#xff08;LeetCode#xff09;
总结#xff1a;解题思路是需要维护一个最大值以及一个最小值#xff0c;因为最小值如果是负数的话乘上接下来的一个负数会有可能成为最大的数
代码#xff1a;
class Solution {
public:int maxProduct(vec…152. 乘积最大子数组 - 力扣LeetCode
总结解题思路是需要维护一个最大值以及一个最小值因为最小值如果是负数的话乘上接下来的一个负数会有可能成为最大的数
代码
class Solution {
public:int maxProduct(vectorint nums) {int n nums.size();if(n 0){return 0;} else if(n 1) {return nums[0];}int p nums[0];int maxP nums[0];int minP nums[0];for(int i 1;i nums.size();i){int tmp maxP;maxP max(max(nums[i],maxP * nums[i]),minP * nums[i]);minP min(min(tmp * nums[i],nums[i]),minP * nums[i]);p max(p ,maxP);}return p;}
};
注意需要用一个临时变量将覆盖前的最大值存储起来以供最小值计算的时候使用因为覆盖前的最大值也可能因为当前的数是一个负数乘上变成最小的。 32. 最长有效括号 - 力扣LeetCode
总结自己一开始的没有考虑清楚如果出现“((()))”这种或者更多对以上括号情况的处理方式。
代码
class Solution {
public:int longestValidParentheses(string s) {if(s.size() 1 || s.size() 0)return 0;vectorint dp(s.size(),0);int res 0;for(int i 1;i s.size();i){if(s[i] )){if(s[i - 1] (){dp[i] (i 2 ? dp[i - 2] : 0) 2;}else if((i - dp[i - 1]) 0 s[i - dp[i - 1] - 1] (){dp[i] dp[i - 1] 2 ((i - dp[i - 1]) 2 ? dp[i - dp[i - 1] - 2] : 0);}}if(dp[i] res)res dp[i];}return res;}
};
注意dp[i - 1] 2 ((i - dp[i - 1]) 2 ? dp[i - dp[i - 1] - 2] : 0);表示在形如....))这种情况下表示倒数第二个括号如果是一个有效子字符串的一部分且在这部分有效子字符串的前面有一个(与倒数第一个)匹配的话那么此时的dp[i] dp[i - 1] 2而在这个(’之前可能符合条件的串所以也加上dp[i - dp[i - 1] - 2]这一部分。
