在Go语言中实现高效的数据结构和算法

func gcd(a, b int) int {
    if b == 0 {
        return a
    }
    return gcd(b, a%b)
}

func maxSubArray(nums []int) int {
    if len(nums) == 0 {
        return 0
    }
    dp := make([]int, len(nums))
    dp[0] = nums[0]
    maxSum := nums[0]
    for i := 1; i < len(nums); i++ {
        dp[i] = max(nums[i], dp[i-1]+nums[i])
        maxSum = max(maxSum, dp[i])
    }
    return maxSum
}

func main() {
    nums := []int{1, 2, 3, 4, 5}
    fmt.Println(nums)           // [1 2 3 4 5]
    nums = append(nums, 6, 7, 8) // 扩容
    fmt.Println(nums)           // [1 2 3 4 5 6 7 8]
}

type IntHeap []int

func (h IntHeap) Len() int           { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h IntHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *IntHeap) Push(x interface{}) {
    *h = append(*h, x.(int))
}

func (h *IntHeap) Pop() interface{} {
    old := *h
    x := old[len(old)-1]
    *h = old[:len(old)-1]
    return x
}

func heapSort(nums []int) []int {
    heapNums := IntHeap(nums)
    heap.Init(&heapNums)

    var result []int
    for heapNums.Len() > 0 {
        result = append(result, heap.Pop(&heapNums).(int))
    }
    return result
}