/dev/bytemap.cc #

算法题：找到整数数组或列表中连续子序列的最大和

Posted on Feb 21, 2025
Table of contents:

题目

此题目需要查找到整数数组或列表中连续子序列的最大和，例如：

示例1：

输入：{-2, 1, -3, 4, -1, 2, 1, -5, 4}  
输出：6
解释：该数组中子序列{4, -1, 2, 1}的和最大

示例2：

输入：{}  
输出：0
注1: 当数组中只存在正整数时情况会比较简单，子数组的最大和也就是整个数组元素的和。
    如果当数组中只包含负整数时，最大和的结果返回 0 即可。
注2: 如果数组为空时，可以认为 0 是其中的最大和，
    所以需要特别注意空列表或数组也是一个有效的子数组或子列表。

要求：

输入范围：数组元素的取值范围为 [-10000, 10000]，数组长度在 [0, 10] 之间。
时间复杂度：O (n)，其中 n 是数组的长度
空间复杂度：O (1)

思路

这个问题是典型的 最大子数组和问题（Maximum Subarray Sum），可以使用 Kadane’s Algorithm 解决。该算法的核心思想是使用动态规划，在遍历数组时维护一个当前子数组的最大和 current_sum，并用 max_sum 记录全局的最大和。

算法步骤

  1. 初始化变量：maxSum = 0, currentSum = 0
  2. 遍历数组:
    • 对当前元素 num，更新 current_sum = max(num, current_sum + num)
    • 更新 max_sum = max(max_sum, current_sum)
  3. 处理空数组的情况，直接返回0。

代码

package main

import "fmt"


func max(a, b int) int {
  if a > b {
    return a
  }

  return b
}

func solution(nums []int) int {
  maxSum := 0
  currentSum := 0

  for _, num := range nums {
    currentSum = max(num, currentSum + num)
    maxSum = max(maxSum, currentSum)
  }

  if maxSum < 0 {
    return 0
  }

  return maxSum
}

func main() {
  nums := []int{-2, 1, -3, 4, -1, 2, 1, -5, 4}
  fmt.Println(solution(nums)) // 6
}