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
}

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
}

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
}

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
}

/**
 * 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))
}