<ruby id="bdb3f"></ruby>

    <p id="bdb3f"><cite id="bdb3f"></cite></p>

      <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
        <p id="bdb3f"><cite id="bdb3f"></cite></p>

          <pre id="bdb3f"></pre>
          <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

          <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
          <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

          <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                <ruby id="bdb3f"></ruby>

                ??碼云GVP開源項目 12k star Uniapp+ElementUI 功能強大 支持多語言、二開方便! 廣告
                # 0152. 乘積最大子數組 ## 題目地址(152. 乘積最大子數組) <https://leetcode-cn.com/problems/maximum-product-subarray/> ## 題目描述 ``` <pre class="calibre18">``` 給你一個整數數組 nums ,請你找出數組中乘積最大的連續子數組(該子數組中至少包含一個數字),并返回該子數組所對應的乘積。 示例 1: 輸入: [2,3,-2,4] 輸出: 6 解釋: 子數組 [2,3] 有最大乘積 6。 示例 2: 輸入: [-2,0,-1] 輸出: 0 解釋: 結果不能為 2, 因為 [-2,-1] 不是子數組。 ``` ``` ## 前置知識 - 滑動窗口 ## 公司 - 阿里 - 騰訊 - 百度 - 字節 ## 思路 這道題目要我們求解連續的 n 個數中乘積最大的積是多少。這里提到了連續,筆者首先想到的就是滑動窗口,但是這里比較特殊,我們不能僅僅維護一個最大值,因此最小值(比如-20)乘以一個比較小的數(比如-10) 可能就會很大。 因此這種思路并不方便。 首先來暴力求解,我們使用兩層循環來枚舉所有可能項,這種解法的時間復雜度是O(n^2), 代碼如下: ``` <pre class="calibre18">``` <span class="hljs-keyword">var</span> maxProduct = <span class="hljs-function"><span class="hljs-keyword">function</span>(<span class="hljs-params">nums</span>) </span>{ <span class="hljs-keyword">let</span> max = nums[<span class="hljs-params">0</span>]; <span class="hljs-keyword">let</span> temp = <span class="hljs-params">null</span>; <span class="hljs-keyword">for</span> (<span class="hljs-keyword">let</span> i = <span class="hljs-params">0</span>; i < nums.length; i++) { temp = nums[i]; <span class="hljs-keyword">for</span> (<span class="hljs-keyword">let</span> j = i + <span class="hljs-params">1</span>; j < nums.length; j++) { temp *= nums[j]; max = <span class="hljs-params">Math</span>.max(temp, max); } } <span class="hljs-keyword">return</span> max; }; ``` ``` 前面說了`最小值(比如-20)乘以一個比較小的數(比如-10)可能就會很大` 。因此我們需要同時記錄乘積最大值和乘積最小值,然后比較元素和這兩個的乘積,去不斷更新最大值。當然,我們也可以選擇只取當前元素。因此實際上我們的選擇有三種,而如何選擇就取決于哪個選擇帶來的價值最大(乘積最大或者最小)。 ![](https://img.kancloud.cn/bc/2c/bc2cf653ac28565f7172c66e943e8f20_603x308.jpg) 這種思路的解法由于只需要遍歷一次,其時間復雜度是O(n),代碼見下方代碼區。 ## 關鍵點 - 同時記錄乘積最大值和乘積最小值## 代碼 代碼支持:Python3,JavaScript Python3 Code: ``` <pre class="calibre18">``` <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">maxProduct</span><span class="hljs-params">(self, nums: List[int])</span> -> int:</span> n = len(nums) max__dp = [<span class="hljs-params">1</span>] * (n + <span class="hljs-params">1</span>) min_dp = [<span class="hljs-params">1</span>] * (n + <span class="hljs-params">1</span>) ans = float(<span class="hljs-string">'-inf'</span>) <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(<span class="hljs-params">1</span>, n + <span class="hljs-params">1</span>): max__dp[i] = max(max__dp[i - <span class="hljs-params">1</span>] * nums[i - <span class="hljs-params">1</span>], min_dp[i - <span class="hljs-params">1</span>] * nums[i - <span class="hljs-params">1</span>], nums[i - <span class="hljs-params">1</span>]) min_dp[i] = min(max__dp[i - <span class="hljs-params">1</span>] * nums[i - <span class="hljs-params">1</span>], min_dp[i - <span class="hljs-params">1</span>] * nums[i - <span class="hljs-params">1</span>], nums[i - <span class="hljs-params">1</span>]) ans = max(ans, max__dp[i]) <span class="hljs-keyword">return</span> ans ``` ``` **復雜度分析** - 時間復雜度:O(N)O(N)O(N) - 空間復雜度:O(N)O(N)O(N) 當我們知道動態轉移方程的時候,其實應該發現了。我們的dp\[i\] 只和 dp\[i - 1\]有關,這是一個空間優化的信號,告訴我們`可以借助兩個額外變量記錄即可`。 Python3 Code: ``` <pre class="calibre18">``` <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">maxProduct</span><span class="hljs-params">(self, nums: List[int])</span> -> int:</span> n = len(nums) a = b = <span class="hljs-params">1</span> ans = float(<span class="hljs-string">'-inf'</span>) <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(<span class="hljs-params">1</span>, n + <span class="hljs-params">1</span>): temp = a a = max(a * nums[i - <span class="hljs-params">1</span>], b * nums[i - <span class="hljs-params">1</span>], nums[i - <span class="hljs-params">1</span>]) b = min(temp * nums[i - <span class="hljs-params">1</span>], b * nums[i - <span class="hljs-params">1</span>], nums[i - <span class="hljs-params">1</span>]) ans = max(ans, a) <span class="hljs-keyword">return</span> ans ``` ``` JavaScript Code: ``` <pre class="calibre18">``` <span class="hljs-keyword">var</span> maxProduct = <span class="hljs-function"><span class="hljs-keyword">function</span>(<span class="hljs-params">nums</span>) </span>{ <span class="hljs-keyword">let</span> max = nums[<span class="hljs-params">0</span>]; <span class="hljs-keyword">let</span> min = nums[<span class="hljs-params">0</span>]; <span class="hljs-keyword">let</span> res = nums[<span class="hljs-params">0</span>]; <span class="hljs-keyword">for</span> (<span class="hljs-keyword">let</span> i = <span class="hljs-params">1</span>; i < nums.length; i++) { <span class="hljs-keyword">let</span> tmp = min; min = <span class="hljs-params">Math</span>.min(nums[i], <span class="hljs-params">Math</span>.min(max * nums[i], min * nums[i])); <span class="hljs-title">// 取最小</span> max = <span class="hljs-params">Math</span>.max(nums[i], <span class="hljs-params">Math</span>.max(max * nums[i], tmp * nums[i])); <span class="hljs-title">/// 取最大</span> res = <span class="hljs-params">Math</span>.max(res, max); } <span class="hljs-keyword">return</span> res; }; ``` ``` **復雜度分析** - 時間復雜度:O(N)O(N)O(N) - 空間復雜度:O(1)O(1)O(1) 更多題解可以訪問我的LeetCode題解倉庫:<https://github.com/azl397985856/leetcode> 。 目前已經30K star啦。 大家也可以關注我的公眾號《腦洞前端》獲取更多更新鮮的LeetCode題解
                  <ruby id="bdb3f"></ruby>

                  <p id="bdb3f"><cite id="bdb3f"></cite></p>

                    <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
                      <p id="bdb3f"><cite id="bdb3f"></cite></p>

                        <pre id="bdb3f"></pre>
                        <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

                        <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
                        <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

                        <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                              <ruby id="bdb3f"></ruby>

                              哎呀哎呀视频在线观看