# Maximum Subarray
> 題目（通常被稱為最大子陣列和問題）

主要考察的是下列的概念
1. 動態規劃 
2. 分治法

並且它還有一個很著名的算法：Kadane’s Algorithm。以下是該題的重點考察概念和解法


## 動態規劃

* 題目的關鍵在於找到一個連續子陣列，使其和最大。
  動態規劃的核心思路是使用遞推方式，逐步找到每個位置的最優解。
* 定義一個動態規劃數組 dp[i]，表示以 nums[i] 結尾的最大子陣列和。遞推關係為
```api
    dp[i] = max(nums[i], dp[i-1] + nums[i])
```
* 如果前一段（即 dp[i-1]）的和加上 nums[i] 還比 nums[i] 自己大，則可以包含 dp[i-1]；否則，就從 nums[i] 開始重新計算子陣列。
* 最後的答案是 dp 數組中的最大值。

## 分治法

  •	另一個可行的解法是使用分治法，類似於歸併排序，將數組分成兩半，分別求解左半部分、右半部分和跨越中間的最大子陣列。
  •	這種方法的時間複雜度為 O(n log n)，不如 Kadane’s Algorithm 高效，但有助於理解分治的思想。


## 題目
[連結](https://leetcode.com/problems/maximum-subarray/description/)

![image](picture.png)

## 自己的理解

### 題目解釋

給訂一組數字找到一組子陣列，這組子陣列的總和是最大的，最後 return 總和。
```go
    nums := []int{-2, 1, -3, 4, -1, 2, 1, -5, 4}
```
在每個迭代中：

	1.	tmpSum += item，將當前元素加到當前子陣列的和中。
	2.	使用 maxSum = max(maxSum, tmpSum) 更新最大和。
	3.	如果 tmpSum < 0，則將 tmpSum 重置為 0，因為負數會拖累之後的累加結果。
![image](picture2.png)