leetcode-go/maximum_subarray/readme.md

1.7 KiB
Raw Permalink Blame History

Maximum Subarray

題目(通常被稱為最大子陣列和問題)

主要考察的是下列的概念

  1. 動態規劃
  2. 分治法

並且它還有一個很著名的算法Kadanes 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),不如 Kadanes Algorithm 高效,但有助於理解分治的思想。

題目

連結

image

自己的理解

題目解釋

給訂一組數字找到一組子陣列,這組子陣列的總和是最大的,最後 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因為負數會拖累之後的累加結果。

image