Golang 用于找到具有长度k的子数组的最大和

在本文中，我们将了解如何使用Go语言中的蛮力法、滑动窗口和前缀和方法来找到具有长度k的子数组的最大和。我们还将讨论每种方法的算法，并提供示例代码来演示它们的实现。

语法

func len(v Type) int

len()函数用于获取任何参数的长度。它接受一个参数作为我们想要找到长度的数据类型变量，并返回整数值，该值是该变量的长度。

示例1

找到长度为k的子数组的最大和的第一个示例是暴力法。

package main

import (
   "fmt"
   "math"
)

func maxSumBruteForce(arr []int, k int) int {
   n := len(arr)
   maxSum := math.MinInt64

   for i := 0; i <= n-k; i++ {
      sum := 0

      for j := i; j < i+k; j++ {
         sum += arr[j]
      }

      if sum > maxSum {
         maxSum = sum
      }
   }
   return maxSum
}

func main() {
   x := []int{1, 2, 3, 4, 5}
   fmt.Println("The given array of integers is:", x)
   var num int = 5
   result := maxSumBruteForce(x, num)
   fmt.Println("The max sum is:", result)
}

输出

The given array of integers is: [1 2 3 4 5]
The max sum is: 15

示例2

在这个示例中，我们将编写一个Go语言程序，通过使用前缀和方法来找到具有k个元素的子数组的最大和。

package main

import (
   "fmt"
   "math"
)

func maxSumPrefixSum(arr []int, k int) int {
   n := len(arr)
   maxSum := math.MinInt64
   prefixSum := make([]int, n+1)

   for i := 1; i <= n; i++ {
      prefixSum[i] = prefixSum[i-1] + arr[i-1]
   }

   for i := k; i <= n; i++ {
      sum := prefixSum[i] - prefixSum[i-k]

      if sum > maxSum {
         maxSum = sum
      }
   }
   return maxSum
}

func main() {
   x := []int{1, 2, 3, 4, 5, 6}
   fmt.Println("The given array of integers is:", x)
   var num int = 6
   result := maxSumPrefixSum(x, num)
   fmt.Println("The max sum is:", result)
}

输出

The given array of integers is: [1 2 3 4 5 6]
The max sum is: 21

结论

在本文中，我们探讨了三种不同的方法来找到给定长度k的子数组的最大和。这里我们使用了两种方法，即暴力方法和前缀和方法。暴力方法的时间复杂度是O(nk)，而前缀和方法的时间复杂度是O(n)。前缀和方法比暴力方法更高效，因为它避免了不必要的计算。