??思維導圖整理大廠面試高頻陣列14: 最大子序積 和 最大子序和 的不同之處, 力扣152??

此專欄文章是對力扣上演算法題目各種方法的總結和歸納, 整理出最重要的思路和知識重點并以思維導圖形式呈現, 當然也會加上我對導圖的詳解.

目的是為了更方便快捷的記憶和回憶演算法重點(不用每次都重復看題解), 畢竟演算法不是做了一遍就能完全記住的. 所以本文適合已經知道解題思路和方法, 想進一步加強理解和記憶的朋友, 并不適合第一次接觸此題的朋友(可以根據題號先去力扣看看官方題解, 然后再看本文內容).

關于本專欄所有題目的目錄鏈接, 刷演算法題目的順序/注意點/技巧, 以及思維導圖源檔案問題請點擊此鏈接.

想進大廠, 刷演算法是必不可少的, 歡迎和博主一起打卡刷力扣演算法, 博主同步更新了演算法視頻講解 和 其他文章/導圖講解, 更易于理解, 歡迎來看!

文章目錄

• • 0.導圖整理
  • 1.與 最大子序和 的不同
  • 2.優化空間
  • 原始碼
  • • Python:
    • java:

題目鏈接:https://leetcode-cn.com/problems/maximum-product-subarray/solution/si-wei-dao-tu-zheng-li-zui-da-zi-xu-ji-h-r8du/

0.導圖整理

1.與 最大子序和 的不同

本題在思想上和 最大子序和 是非常相似的, 甚至連定義dp陣列及下標的含義都是相同的: 用fmax(i)來表示以第 i 個元素結尾的乘積最大子陣列的乘積, ai表示輸入引數 nums.

但是如果直接根據經驗寫出這樣的狀態轉移方程: fmax(i)=max{f(i?1)+ai,ai}是錯誤的, 用比較專業的語言解釋就是: 這里的定義并不滿足「最優子結構」, 當前位置的最優解未必是由前一個位置的最優解轉移得到的. 用白話來解釋就是: 兩個負數相乘有可能會得到更大的結果, 當前的最大值并不一定是通過上個狀態的最大值決定的, 也可能是上個狀態的最小值決定的. 這都是因為加法和乘法的不同性質決定的.

通過這樣的分析就決定了我們還必須同時維護上個狀態的最小值, 然后就可以寫出如下的狀態轉移方程了:

它代表第i個元素結尾的乘積最大子陣列的乘積fmax(i), 可以考慮把ai加入第 i?1 個元素結尾的乘積最大或最小的子陣列的乘積中, 二者加上ai, 三者取大, 就是第i個元素結尾的乘積最大子陣列的乘積. 第i個元素結尾的乘積最小子陣列的乘積fmin(i)同理.

這是兩者思想上的不同, 在實作代碼上, 也有著一點差別, 在沒有進行空間優化之前, 我們是需要維護兩個dp陣列的, 而且這兩個陣列是完全獨立的, 這就說明我們不能通過陣列的參考這種淺拷貝的方式來操作陣列, 必須將陣列進行真實的復制(深拷貝)之后再進行相關的操作, 這就是如下代碼的含義:

System.araycopy(nums, 0, maxF, 0, length);//nums從0開始的位置復制到maxF從0開始的位置,長度length
System.araycopy(nums, 0, minF, 0, length);//對陣列進行深拷貝,不能簡單的使用陣列的參考(淺拷貝)

2.優化空間

當然本題是可以像 最大子序和 一樣進行空間優化的, 上面講述的深拷貝的思想, 是為了讓大家有這種意識, 在不能進行空間優化的時候該如何進行處理.

本題的優化也是挺簡單的, 只需要用兩個變數來維護i?1時刻的兩種狀態即可.

這里有個Python和java語言的注意點: java中的max/min函式只能包含兩個引數, 當含有有個變數時, 要先進行兩兩比較, 再將比較之后的結果和其他變數再比較, 而Python中的可以包含任意個引數, 直接一起比較即可.

原始碼

Python:

# 優化空間
class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        maxF, minF, ans = nums[0], nums[0], nums[0]
        length = len(nums)
        for i in range(1, length):
            mx, mn = maxF, minF # 只用兩個變數來維護i?1時刻的狀態,優化空間
            maxF = max(mx * nums[i], nums[i], mn * nums[i])
            minF = min(mn * nums[i], nums[i], mx * nums[i])
            ans = max(maxF, ans)
        
        return ans

java:

// 未優化空間
class Solution {
    public int maxProduct(int[] nums) {
        int length = nums.length;
        int[] maxF = new int[length];
        int[] minF = new int[length];//以第i個元素結尾的乘積最小子陣列的乘積
        System.araycopy(nums, 0, maxF, 0, length);//nums從0開始的位置復制到maxF從0開始的位置,長度length
        System.araycopy(nums, 0, minF, 0, length);//對陣列進行深拷貝,不能簡單的使用陣列的參考(淺拷貝)
        for (int i = 1; i < length; ++i) {
            //兩個狀態轉移方程
            maxF[i] = Math.max(maxF[i - 1] * nums[i], Math.max(nums[i], minF[i - 1] * nums[i]));
            minF[i] = Math.min(minF[i - 1] * nums[i], Math.min(nums[i], maxF[i - 1] * nums[i]));
        }
        int ans = maxF[0];
        for (int i = 1; i < length; ++i) {
            ans = Math.max(ans, maxF[i]);
        }
        return ans;
    }
}

// 優化空間
class Solution {
    public int maxProduct(int[] nums) {
        int maxF = nums[0], minF = nums[0], ans = nums[0];
        int length = nums.length;
        for (int i = 1; i < length; ++i) {
            int mx = maxF, mn = minF;//只用兩個變數來維護i?1時刻的狀態,優化空間
            maxF = Math.max(mx * nums[i], Math.max(nums[i], mn * nums[i]));
            minF = Math.min(mn * nums[i], Math.min(nums[i], mx * nums[i]));
            ans = Math.max(maxF, ans);
        }
        return ans;
    }
}

我的更多精彩文章鏈接, 歡迎查看

各種電腦/軟體/生活/音樂/動漫/電影技巧匯總(你肯定能夠找到你需要的使用技巧)

力扣演算法刷題 根據思維導圖整理筆記快速記憶演算法重點內容(歡迎和博主一起打卡刷題哦)

計算機專業知識 思維導圖整理

最值得收藏的 Python 全部知識點思維導圖整理, 附帶常用代碼/方法/庫/資料結構/常見錯誤/經典思想(持續更新中)

最值得收藏的 C++ 全部知識點思維導圖整理(清華大學鄭莉版), 東南大學軟體工程初試906科目

最值得收藏的 計算機網路 全部知識點思維導圖整理(王道考研), 附帶經典5層結構中英對照和框架簡介

最值得收藏的 演算法分析與設計 全部知識點思維導圖整理(北大慕課課程)

最值得收藏的 資料結構 全部知識點思維導圖整理(王道考研), 附帶經典題型整理

最值得收藏的 人工智能導論 全部知識點思維導圖整理(王萬良慕課課程)

最值得收藏的 數值分析 全部知識點思維導圖整理(東北大學慕課課程)

最值得收藏的 數字影像處理 全部知識點思維導圖整理(武漢大學慕課課程)

紅黑樹 一張導圖解決紅黑樹全部插入和洗掉問題 包含詳細操作原理 情況對比

各種常見排序演算法的時間/空間復雜度 是否穩定 演算法選取的情況 改進 思維導圖整理

人工智能課件 演算法分析課件 Python課件 數值分析課件 機器學習課件 影像處理課件

考研相關科目 知識點 思維導圖整理

考研經驗–東南大學軟體學院軟體工程(這些基礎課和專業課的各種坑和復習技巧你應該知道)

東南大學 軟體工程 906 資料結構 C++ 歷年真題 思維導圖整理

東南大學 軟體工程 復試3門科目歷年真題 思維導圖整理

最值得收藏的 考研高等數學 全部知識點思維導圖整理(張宇, 湯家鳳), 附做題技巧/易錯點/知識點整理

最值得收藏的 考研線性代數 全部知識點思維導圖整理(張宇, 湯家鳳), 附帶慣用思維/做題技巧/易錯點整理

高等數學 中值定理 一張思維導圖解決中值定理所有題型

考研思修 知識點 做題技巧 同類比較 重要會議 1800易錯題 思維導圖整理

考研近代史 知識點 做題技巧 同類比較 重要會議 1800易錯題 思維導圖整理

考研馬原 知識點 做題技巧 同類比較 重要會議 1800易錯題 思維導圖整理

考研數學課程筆記 考研英語課程筆記 考研英語單詞詞根詞綴記憶 考研政治課程筆記

Python相關技術 知識點 思維導圖整理

Numpy常見用法全部OneNote筆記 全部筆記思維導圖整理

Pandas常見用法全部OneNote筆記 全部筆記思維導圖整理

Matplotlib常見用法全部OneNote筆記 全部筆記思維導圖整理

PyTorch常見用法全部OneNote筆記 全部筆記思維導圖整理

Scikit-Learn常見用法全部OneNote筆記 全部筆記思維導圖整理

Java相關技術/ssm框架全部筆記

Spring springmvc Mybatis jsp

科技相關 小米手機

小米 紅米 歷代手機型號大全 發布時間 發布價格

常見手機品牌的各種系列劃分及其特點

歷代CPU和GPU的性能情況和常見后綴的含義 思維導圖整理