leetcode-go/maximum_subarray

Maximum Subarray

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

主要考察的是下列的概念

1. 動態規劃
2. 分治法

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

動態規劃

• 題目的關鍵在於找到一個連續子陣列，使其和最大。 動態規劃的核心思路是使用遞推方式，逐步找到每個位置的最優解。
• 定義一個動態規劃數組 dp[i]，表示以 nums[i] 結尾的最大子陣列和。遞推關係為

    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 高效，但有助於理解分治的思想。

題目

連結

自己的理解

題目解釋

給訂一組數字找到一組子陣列，這組子陣列的總和是最大的，最後 return 總和。

    nums := []int{-2, 1, -3, 4, -1, 2, 1, -5, 4}

在每個迭代中：

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