Week 19 @ 2025 算法周记【最大子数组和 + 括号 + 二叉树】
最大子数组和
LC 53. Maximum Subarray 最大子数组和
https://leetcode.com/problems/maximum-subarray/
动态规划 (Kadane's algorithm)
func maxSubArray(nums []int) int {
dp := make([]int, len(nums)) // 以 i 结尾的最大 sum
dp[0] = nums[0]
for i := 1; i < len(nums); i++ {
dp[i] = max(nums[i], dp[i-1] + nums[i])
}
return slices.Max(dp)
}滑动窗口
func maxSubArray(nums []int) int {
left, right := 0, 0
maxSum := nums[0]
windowSum := 0
for right < len(nums) {
windowSum += nums[right]
right++
maxSum = max(maxSum, windowSum)
for left < right && windowSum < 0 {
windowSum -= nums[left]
left++
}
}
return maxSum
}分治（线段树）
TODO https://leetcode.cn/problems/maximum-subarray/solutions/228009/zui-da-zi-xu-he-by-leetcode-solution/
LC 918. Maximum Sum Circular Subarray 环形子数组的最大和
https://leetcode.com/problems/maximum-sum-circular-subarray/description/
分开考虑
func maxSubarraySumCircular(nums []int) int {
n := len(nums)
maxSum := nums[0]
pre := nums[0]
preSum := nums[0]
preSumMax := make([]int, n)
preSumMax[0] = preSum
for i := 1; i < len(nums); i++ {
pre = nums[i] + max(pre, 0)
maxSum = max(maxSum, pre)
preSum += nums[i]
preSumMax[i] = max(preSum, preSumMax[i-1])
}
postSum := 0
for i := n-1; i > 0; i-- {
postSum += nums[i]
maxSum = max(maxSum, postSum + max(preSumMax[i-1], 0))
}
return maxSum
}
单调队列
func maxSubarraySumCircular(nums []int) int {
n := len(nums)
preSum := make([]int, 2*n)
preSum[0] = nums[0]
for i := 1; i < n; i++ {
preSum[i] = preSum[i-1] + nums[i]
}
for i, num := range nums {
preSum[n+i] = preSum[n+i-1] + num
}
maxSum := nums[0]
window := NewMonotonicQueue()
window.Push(0)
for i := 0; i < len(preSum); i++ {
maxSum = max(maxSum, preSum[i] - window.Min())
window.Push(preSum[i])
if window.Size() > n {
window.Pop()
}
}
return maxSum
}
type MonotonicQueue struct {
q []int
maxq []int
minq []int
}
func NewMonotonicQueue() *MonotonicQueue {
return &MonotonicQueue{
q: []int{},
maxq: []int{},
minq: []int{},
}
}
func (q *MonotonicQueue) Push(elem int) {
q.q = append(q.q, elem)
// maxq: 5 3 3 1
for len(q.maxq) > 0 && q.maxq[len(q.maxq)-1] < elem {
q.maxq = q.maxq[:len(q.maxq)-1]
}
q.maxq = append(q.maxq, elem)
// minq: 1 3 3 5
for len(q.minq) > 0 && q.minq[len(q.minq)-1] > elem {
q.minq = q.minq[:len(q.minq)-1]
}
q.minq = append(q.minq, elem)
}
func (q *MonotonicQueue) Pop() int {
elem := q.q[0]
q.q = q.q[1:]
if q.maxq[0] == elem {
q.maxq = q.maxq[1:]
}
if q.minq[0] == elem {
q.minq = q.minq[1:]
}
return elem
}
func (q *MonotonicQueue) Max() int {
return q.maxq[0]
}
func (q *MonotonicQueue) Min() int {
return q.minq[0]
}
func (q *MonotonicQueue) Size() int {
return len(q.q)
}
func (q *MonotonicQueue) IsEmpty() bool {
return len(q.q) == 0
}括号类问题
LC 921. Minimum Add to Make Parentheses Valid 使括号有效的最少添加
https://leetcode.com/problems/minimum-add-to-make-parentheses-valid/description/
func minAddToMakeValid(s string) (count int) {
lefts := 0
for _, b := range s {
if b == '(' {
lefts++
} else {
if lefts > 0 {
lefts--
} else {
count++
}
}
}
count += lefts
return
}LC 1541. Minimum Insertions to Balance a Parentheses String 平衡括号字符串的最少插入次数
https://leetcode.com/problems/minimum-insertions-to-balance-a-parentheses-string/description/
func minInsertions(s string) int {
lefts := 0
count := 0
i := 0
for i < len(s) {
if s[i] == '(' {
lefts++
i++
} else {
if i+1 < len(s) && s[i+1] == ')' {
// 找到 ))
if lefts == 0 {
count++
} else {
lefts--
}
i += 2
} else {
// 只找到一个 )
if lefts == 0 {
count += 2 // 需要补一个 ( 和一个 )
} else {
count++
lefts--
}
i++
}
}
}
count += lefts * 2 // 每一个 ( 需要补两个 ))
return count
}LC 104. Maximum Depth of Binary Tree 二叉树的最大深度
https://leetcode.com/problems/maximum-depth-of-binary-tree/
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func maxDepth(root *TreeNode) int {
if root == nil {
return 0
}
return 1 + max(maxDepth(root.Left), maxDepth(root.Right))
}
, multiple selections available,