[Day 11] Leetcode 152. Maximum Product Subarray (C++)

前言

先来个之前写过觉得还算值得练习的DP题目~152. Maximum Product Subarray,之前一时看了没有头绪该怎麽写,把经过过程写下来~

解法

本来看到题目转过很多想法~ 想说都是整数,那只要结果是正的&不是0,都是越长越好,所以可能可以预设全部相乘,这个当暂存的最大值(greedy魂上身):如果是0或是负的再去检查;是负的就从两边找到第一个负的看哪边乘起来比较大就不要,变回原本问题,更新最大值之後继续找,就是从两边去削减,直到变成正的或是整条都没了;是0的就看从哪边去掉0比较不伤(直接比两边结果),但想不出来怎麽实现,所以看了别人的想法当提示,我现在也来当那个别人,说不定看到这个想法就可以解出来了~

  • 解法一
    • 使用DP内存两个值,纪录包含该位置值的最大乘积跟最小乘积,然後每次就考虑最大乘积跟最小乘积的更新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;
    }
};
  • 解法二
    • 另外一个酷解法(应该算是greedy),直接用两次for回圈,用类似累加的方式来greedy解。其实它的概念很简单,就是maxima array不是靠左就是靠右,不会有在中间的情形(因为乘越多越好,要舍弃的情形只有是负数或是0的情形,而负数的话如果两边都要舍那应该两边都包含进去),0的情形另外考虑:如果有0的那段砍掉,就变成原问题,程序码如下:
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)改天把他补上~


<<:  Day 1 转职之路

>>:  第十一天:用 TDD 实作购物车类别

【D5】取得厨房钥匙:下载凭证

前言 当我们已经可以进入shioaji这个厨房,却发现用来烹饪的厨具都锁在架上,我们只能用一些简单的...

DeBug Day 26

修正Bug日 [ ] 修正首页的排版问题 [ ] 修正书本细节页面的排版问题 [ ] 修正新增照片到...

【Day 30】- 结语 : 从 0 开始的网路爬虫

结语   完成了连续一个月的铁人赛了!当初觉得每天发一篇应该不会太难,甚至还在开赛前屯了四篇,结果事...

完赛心得

首先很感谢it铁人赛给予我这个机会,让我做到平时连想不会想到的事。因为对於我而言,实在是没什麽能够说...

[Day02] Tableau 轻松学 - Tableau 介绍

Tableau 优点 Tableau 是一种企业级的商业智能 (BI, Business Intel...