動态規劃是面試中常考的知識點，特别是一些互聯網大廠的面試，可以說必會考到一道涉及動态規劃的算法題，因此掌握動态規劃，能提高面試的通過率。

本文的内容為通過一道騰訊的面試題，即力扣 152. 乘積最大子數組，由暴力法求解一步一步演化到由動态規劃進行求解來介紹動态規劃。

給你一個整數數組 nums ，請你找出數組中乘積最大的連續子數組（該子數組中至少包含一個數字），并返回該子數組所對應的乘積。

示例

注意點

本題要求的是乘積最大的連續子數組而不是乘積最大的子序列，因此要求子數組中的元素在原數組中是連續的。

思考：整數數組可能存在的情況

由于題目已明确告知子數組中至少包含一個數字，因此主要存在以下兩種情況：

整數數組 nums 中隻包含一個元素；

整數數組 nums 中包含兩個或兩個以上元素。

隻包含一個元素，直接返回該元素；

包含兩個或兩個以上元素，暴力輪詢或動态規劃求乘積最大的連續子數組，返回乘積。

暴力法

初看該題，很容易想到可以通過暴力法去求解，即通過兩層循環遍曆整個數組。

Show me the Code

C

上面是通過暴力法去求解，由于進行了兩層遍曆，因此該解法的時間複雜度為O(n^2)，但由于未開辟額外的空間，所以空間複雜度為O(1)。但在面試過程中，如果提供這種解法，面試官往往會問還有沒有更優的解法？也就是說面試官對當前的解法（時間複雜度過高）不太滿意。

那有沒有更優的解法呢？當然有！對動态規劃有所了解的童鞋，在看到題目中的最大兩個字，自然會想到通過動态規劃去求解，因為涉及到求最優的問題，往往可以通過動态規劃去解。

由于整數數組 nums 中的元素可能有正數、負數和 0，因此連續子數組中的元素也可能是這三種情況。

如果連續子數組中的元素存在負數，正數乘以負數就成負數，那麼最大值乘以負數就變成了最小值，因此需要同時考慮當前連續子數組乘積的最大值curMax和最小值curMin。

注意點

整數數組 nums 中存在負數，當遍曆到以nums[i]（負數）結尾連續子數組時，需要交換 curMax 和 curMin。

舉栗

以整數數組nums = [2, 3, -2, 4]為栗子，求乘積最大子數組的乘積。

如下圖示

代碼示例：

C

C語言

采用動态規劃的方法去求解，由于隻進行了一層遍曆，因此其時間複雜度為O(n)，同樣由于未開辟額外的空間，所以空間複雜度為O(1)。

今天的分享就到這裡了，大家要好好學C 喲~

寫在最後：對于準備學習C/C 編程的小夥伴，如果你想更好的提升你的編程核心能力（内功）不妨從現在開始！

編程學習書籍分享：

編程學習視頻分享：

整理分享（多年學習的源碼、項目實戰視頻、項目筆記，基礎入門教程）

歡迎轉行和學習編程的夥伴，利用更多的資料學習成長比自己琢磨更快哦！

對于C/C 感興趣可以關注小編在後台私信我：【編程交流】一起來學習哦！可以領取一些C/C 的項目學習視頻資料哦！已經設置好了關鍵詞自動回複，自動領取就好了！