---

highlight: xcode theme: channing-cyan

---

攜手創作，共同成長！這是我參與「掘金日新計劃 · 8 月更文挑戰」的第15天，點選檢視活動詳情 。如果哪裡寫的不對，請大家評論批評。

最大子陣列和

題目

給你一個整數陣列 nums ，請你找出一個具有最大和的連續子陣列（子陣列最少包含一個元素），返回其最大和。

子陣列 是陣列中的一個連續部分。

示例 1

js 輸入：nums = [-2,1,-3,4,-1,2,1,-5,4] 輸出：6 解釋：連續子陣列 [4,-1,2,1] 的和最大，為 6 。

示例 2：

js 輸入：nums = [1] 輸出：1

示例 3：

js 輸入：nums = [5,4,-1,7,8] 輸出：23

分析

動態規劃

1. 動態規劃(Dynamic Programming)演算法的核心思想是：將大問題劃分為小問題進行解決，從而一步步獲取最優解的處理演算法
2. 動態規劃可以通過填表的方式來逐步推進，得到最優解.

圖解

1. 定義dp陣列： ```js
2. dp[i]表示nums中以nums[i]結尾的最大子序和。
3. dp[i]中最大的元素即為nums的最大子序和。
4. dp[0] = nums[0] ```
5. 可以得到公式 $$ dp[i]=max(dp[i−1]+nums[i],nums[i]) $$
6. 第一步，初始化一個新的陣列來儲存[i]結尾的最大子序和var dp = Array(repeating: 0, count: nums.count)
7. dp[0]存放nums[0]作為單個子序時的和，可以減少一次迴圈，dp[0] = nums[0]
8. 定義最大子序和max_num，暫時儲存nums[0]的陣列，也可以防止陣列只有一位資料

9. 開始迴圈，進入圖解

10. 第一步迴圈：取值為1，dp[1] = max(dp[0] + nums[1],nums[1])轉換一下dp[1] = max(-2 + 1,1) = 1，max_num = max(-2, 1) = 1

11. 第二步迴圈：取值為-3，dp[2] = max(dp[1] + nums[2],nums[2])轉換一下dp[2] = max(1 -3,-3) = -2，max_num = max(1, -2) = 1

12. 第三步迴圈：取值為4，dp[3] = max(dp[2] + nums[3],nums[3])轉換一下dp[3] = max(-2 + 4,4) = 4，max_num = max(1, 4) = 4

13. 第四步迴圈：取值為-1，dp[4] = max(dp[3] + nums[4],nums[4])轉換一下dp[4] = max(4+-1,-1) = 3，max_num = max(4, 3) = 4

14. 第五步迴圈：取值為2，dp[5] = max(dp[4] + nums[5],nums[5])轉換一下dp[5] = max(3+2,2) = 5，max_num = max(4, 5) = 5

15. 第六步迴圈：取值為1，dp[6] = max(dp[5] + nums[6],nums[6])轉換一下dp[6] = max(5+1,1) = 6，max_num = max(5, 6) = 6

16. 第七步迴圈：取值為-5，dp[7] = max(dp[6] + nums[7],nums[7])轉換一下dp[7] = max(6 - 5, -5) = 1，max_num = max(6, 1) = 6

17. 第八步迴圈：取值為4，dp[8] = max(dp[7] + nums[8],nums[8])轉換一下dp[8] = max(1+4, 1) = 5，max_num = max(6, 5) = 6

程式碼

```js

class Solution { func maxSubArray(_ nums: [Int]) -> Int { guard nums.count > 0 else { return Int.min } var dp = Array(repeating: 0, count: nums.count) dp[0] = nums[0] var max_num = res[0] for i in 1..<nums.count { dp[i] = max(dp[i - 1] + nums[i],nums[i]) max_num = max(max_num, dp[i]) } return max_num } } ```