Kadane's 算法是一种用于解决最大子数组和问题（Maximum Subarray Problem）的高效算法。它的时间复杂度为 O(n)，空间复杂度为 O(1)，是解决这类问题的经典方法。

---

问题描述

给定一个整数数组 nums，找到一个具有最大和的连续子数组（子数组至少包含一个元素），返回其最大和。

示例：

输入: nums = [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

---

Kadane's 算法的核心思想

Kadane's 算法的核心思想是通过动态规划的思想，逐步计算以每个位置为结尾的最大子数组和，同时用一个变量记录全局的最大子数组和。

动态规划状态定义

• 定义 dp[i] 表示以第 i 个元素结尾的最大子数组和。
• 状态转移方程为：

  dp[i] = max(nums[i], dp[i-1] + nums[i])

  解释：
  • 如果 dp[i-1] 是负数，那么以 nums[i] 结尾的最大子数组和就是 nums[i] 本身。
  • 如果 dp[i-1] 是正数，那么以 nums[i] 结尾的最大子数组和就是 dp[i-1] + nums[i]。

优化空间复杂度

由于 dp[i] 只依赖于 dp[i-1]，我们可以用一个变量 currentMax 来代替 dp[i]，从而将空间复杂度优化为 O(1)。

---

Kadane's 算法的步骤

1. 初始化两个变量：
   • currentMax：表示以当前元素结尾的最大子数组和。
   • globalMax：表示全局的最大子数组和。
2. 遍历数组中的每个元素：
   • 更新 currentMax：currentMax = max(nums[i], currentMax + nums[i])。
   • 更新 globalMax：globalMax = max(globalMax, currentMax)。
3. 返回 globalMax。

---

Kadane's 算法的代码实现

func maxSubArray(nums []int) int {
    if len(nums) == 0 {
        return 0
    }
    
    currentMax := nums[0] // 以当前元素结尾的最大子数组和
    globalMax := nums[0]  // 全局的最大子数组和
    
    for i := 1; i < len(nums); i++ {
        // 更新 currentMax
        currentMax = max(nums[i], currentMax + nums[i])
        // 更新 globalMax
        globalMax = max(globalMax, currentMax)
    }
    
    return globalMax
}

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

---

示例解析

以 nums = [-2,1,-3,4,-1,2,1,-5,4] 为例：

索引 (i)	nums[i]	currentMax (以 nums[i] 结尾的最大和)	globalMax (全局最大和)
0	-2	-2	-2
1	1	max(1, -2 + 1) = 1	max(-2, 1) = 1
2	-3	max(-3, 1 + -3) = -2	max(1, -2) = 1
3	4	max(4, -2 + 4) = 4	max(1, 4) = 4
4	-1	max(-1, 4 + -1) = 3	max(4, 3) = 4
5	2	max(2, 3 + 2) = 5	max(4, 5) = 5
6	1	max(1, 5 + 1) = 6	max(5, 6) = 6
7	-5	max(-5, 6 + -5) = 1	max(6, 1) = 6
8	4	max(4, 1 + 4) = 5	max(6, 5) = 6

最终结果为 6，对应的子数组是 [4, -1, 2, 1]。

---

Kadane's 算法的变种

Kadane's 算法可以扩展到解决一些变种问题，例如：

1. 环形数组的最大子数组和：

   • 计算普通数组的最大子数组和 maxSum。
   • 计算普通数组的最小子数组和 minSum。
   • 计算数组的总和 totalSum。
   • 如果 maxSum > 0，则环形数组的最大子数组和为 max(maxSum, totalSum - minSum)。
   • 如果 maxSum < 0，则环形数组的最大子数组和为 maxSum。

2. 返回最大子数组的起始和结束位置：

   • 在更新 currentMax 和 globalMax 时，记录子数组的起始和结束位置。

---

总结

• Kadane's 算法通过动态规划的思想，高效地解决了最大子数组和问题。
• 它的时间复杂度为 O(n)，空间复杂度为 O(1)。
• 通过简单的修改，可以扩展到解决环形数组等变种问题。