[TOC]

一猿推、題目描述

給定一個(gè)整數(shù)數(shù)組 nums ，找出一個(gè)序列中乘積最大的連續(xù)子序列（該序列至少包含一個(gè)數(shù)）。

示例 1:

輸入: [2,3,-2,4]
輸出: 6
解釋: 子數(shù)組 [2,3] 有最大乘積 6。

示例 2:

輸入: [-2,0,-1]
輸出: 0
解釋: 結(jié)果不能為 2, 因?yàn)?[-2,-1] 不是子數(shù)組。

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/maximum-product-subarray
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有欺旧。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處蛤签。

二辞友、解題方法

1. 暴力法（超時(shí)）

思路：

暴力出奇跡，這是我這種弟弟總是第一時(shí)間想到的東西震肮。既然你要乘積最大的連續(xù)子序列称龙，我將所有的乘積保存下來，再取最大的豈不簡(jiǎn)單粗暴戳晌？
只要令表示從到的乘積即可鲫尊，則顯然：

當(dāng)然，不用問的沦偎，暴力怎么可能會(huì)出得了奇跡疫向？

時(shí)間復(fù)雜度：咳蔚，空間復(fù)雜度：。

代碼：

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        if (nums.empty())   return 0;

        auto ans = nums[0];
        vector<vector<int>> dp(nums.size(), vector<int>(nums.size(), 0));
        for (auto i = 0; i < nums.size(); ++i) {
            dp[i][i] = nums[i];
            ans = max(ans, nums[i]);
        }
        for (auto diff = 1; diff < nums.size(); ++diff) {
            for (auto i = 0; i + diff < nums.size(); ++i) {
                dp[i][i + diff] = dp[i][i + diff - 1] * nums[i + diff];
                ans = max(ans, dp[i][i + diff]);
            }
        }
        return ans;
    }
};

2. 數(shù)學(xué)搔驼？谈火？？

思路：

既然暴力法沒轍了舌涨，那我們就稍微分析一下問題吧糯耍。

題目說，這是一個(gè)整數(shù)數(shù)組囊嘉。
相信能做這道題目的人谍肤，一定能理解因?yàn)槭沁B乘，所以在不考慮的情況下一定是越多的整數(shù)相乘哗伯，得到的結(jié)果的絕對(duì)值越大，最后無非是正負(fù)的問題篷角。
同樣焊刹，負(fù)負(fù)得正，所以如果是偶數(shù)個(gè)負(fù)數(shù)的情況恳蹲，我們只要一股腦全乘起來就好了虐块，一定是最大的。而如果是奇數(shù)個(gè)負(fù)數(shù)的情況嘉蕾，要么放棄第一個(gè)負(fù)數(shù)贺奠，要么放棄最后一個(gè)負(fù)數(shù)，取二者中能得到的最大乘積错忱。
如果要考慮儡率，由于會(huì)將乘積變?yōu)?img class="math-inline" src="https://math.jianshu.com/math?formula=0" alt="0" mathimg="1">，我們可以利用將數(shù)組進(jìn)行分割以清，在每一個(gè)子數(shù)組中儿普，利用上述結(jié)論即可。

時(shí)間復(fù)雜度：掷倔，空間復(fù)雜度：

代碼：

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        if (nums.empty())   return 0;
        
        auto ans = nums[0], product = 1;
        // 從左往右掃描眉孩，等價(jià)于奇數(shù)情況放棄最右邊負(fù)數(shù)
        for (auto i = 0; i < nums.size(); ++i) {
            product *= nums[i];
            ans = ans > product ? ans : product;
            product = product == 0 ? 1 : product;
        }
        product = 1;
        // 從右往左掃描，等價(jià)于奇數(shù)情況放棄最左邊負(fù)數(shù)
        for (auto i = int(nums.size()) - 1; i > -1; --i) {
            product *= nums[i];
            ans = ans > product ? ans : product;
            product = product == 0 ? 1 : product;
        }
        return ans;
    }
};

3. 動(dòng)態(tài)規(guī)劃

思路：

這次是真動(dòng)態(tài)規(guī)劃勒葱，不是解法1那個(gè)假洋鬼子浪汪。

還記得最大子序和這一題嗎？它有動(dòng)態(tài)規(guī)劃的解凛虽。這一題跟它好像很類似死遭？只不過一個(gè)求和一個(gè)求積，或許我們可以采取類似的方法來解這一題涩维？

假如類比過來殃姓，我們采用表示到為止的乘積最大值袁波，我們并不能像求和一樣令：

因?yàn)槌朔ù嬖谪?fù)負(fù)得正的情況，哪怕當(dāng)前是負(fù)數(shù)蜗侈，指不準(zhǔn)下面掃描到一個(gè)負(fù)數(shù)立馬就變成了正的最大值了呢篷牌？所以我們必須要能保存已經(jīng)出現(xiàn)的最小值的情況，同時(shí)踏幻，因?yàn)樽畲笾岛妥钚≈悼赡軙?huì)互換枷颊，我們還需要保存已經(jīng)出現(xiàn)的最大值的情況。
令该面、分別表示掃描到為止的最大值和最小值夭苗，則我們有：


這里的和可以用來處理掉的情況，否則一旦出現(xiàn)就全完了隔缀。

看得出來题造，由于我們只需要使用到和，所以我們可以將狀態(tài)壓縮到和兩個(gè)變量猾瘸，來節(jié)約開辟數(shù)組的內(nèi)存界赔。

時(shí)間復(fù)雜度：，空間復(fù)雜度：

代碼：

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        if (nums.empty())
            return 0;

        auto ans = numeric_limits<int>::min();
        auto pos = 1, neg = 1;
        for (auto &num : nums) {
            if (num < 0)    swap(pos, neg);
            pos = max(pos * num, num);
            neg = min(neg * num, num);
            ans = max(pos, ans);
        }
        return ans;
    }
};