47 lines
1.7 KiB
Markdown
47 lines
1.7 KiB
Markdown
|
# 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/)
|
|||
|
|
|
|||
|
|
|
|||
|
|
|
|||
|
|
## 自己的理解
|
|||
|
|
|
|||
|
|
### 題目解釋
|
|||
|
|
|
|||
|
|
給訂一組數字找到一組子陣列，這組子陣列的總和是最大的，最後 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，因為負數會拖累之後的累加結果。
|
|||
|
|
|