小狐狸能量森林冒险

怎样从“正数 = 能量果实，负数 = 荆棘陷阱。找出一段连续旅程，使总体力收益最高。”推导出 能量森林 · Kadane，并证明每次状态变化都不会漏掉答案？

中心结论：current = 当前连续冲刺段的能量；best = 历史最高。若 current + nums[i] 不如 nums[i]，说明前缀拖后腿，从 i 重新起跑。

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

在本站主例中，正数 = 能量果实，负数 = 荆棘陷阱。找出一段连续旅程，使总体力收益最高。

算法最终需要得到或观察：bestSum = 6，bestSegment = [4,-1,2,1]。

1func maxSubArray(nums []int) int {
2    current := nums[0]
3    best := nums[0]
4
5    for i := 1; i < len(nums); i++ {
6        if current + nums[i] < nums[i] {
7            current = nums[i]
8        } else {
9            current = current + nums[i]
10        }
11
12        if current > best {
13            best = current
14        }
15    }
16
17    return best
18}

直接递归会反复求同一个子问题；动态规划把答案写入状态表并按依赖顺序复用。

暴力方案的价值是确认题意并提供正确性基线。它通常会覆盖所有候选， 但没有保存已经确认的信息，因此同一状态会被重新计算。

1func maxSubArray(nums []int) int {
2    current := nums[0]
3    best := nums[0]
4
5    for i := 1; i < len(nums); i++ {
6        if current + nums[i] < nums[i] {
7            current = nums[i]
8        } else {
9            current = current + nums[i]
10        }
11
12        if current > best {
13            best = current
14        }
15    }
16
17    return best
18}

1. 1建模把输入翻译成“状态表账本”，明确答案需要观察什么。
2. 2状态只维护 current 描述当前链条能量，best 是全程最高记录。
3. 3转移每一步按照 current = 当前连续冲刺段的能量；best = 历史最高。若 current + nums[i] 不如 nums[i]，说明前缀拖后腿，从 i 重新起跑。
4. 4收尾读取 bestSum = 6，bestSegment = [4,-1,2,1]。，并复核边界与复杂度。

先写清 dp 状态含义，再推导转移、初值和遍历顺序。

这道题不是为了记住一个组件名称，而是为了让状态具有可解释的语义：current 描述当前链条能量，best 是全程最高记录。

1func maxSubArray(nums []int) int {
2    current := nums[0]
3    best := nums[0]
4
5    for i := 1; i < len(nums); i++ {
6        if current + nums[i] < nums[i] {
7            current = nums[i]
8        } else {
9            current = current + nums[i]
10        }
11
12        if current > best {
13            best = current
14        }
15    }
16
17    return best
18}

这一题可以用 DP 求解也可以不用 DP。 题目要求输出数组中某个区间内数字之和最大的那个值。`dp[i]` 表示 `[0,i]` 区间内各个子区间和的最大值，状态转移方程是 `dp[i] = nums[i] + dp[i-1] (dp[i-1] > 0)`，`dp[i] = nums[i] (dp[i-1] ≤ 0)`。

current = 当前连续冲刺段的能量；best = 历史最高。若 current + nums[i] 不如 nums[i]，说明前缀拖后腿，从 i 重新起跑。

执行过程中持续维护：current 描述当前链条能量，best 是全程最高记录。

正确性依赖以下不变量：cur 只关心以 i 结尾的最优,负贡献前缀被丢弃。

面试时可以压缩为：Kadane O(n):cur=max(nums[i],cur+nums[i]),ans=max(ans,cur)。

落到当前题，执行机制可以压缩为：current = 当前连续冲刺段的能量；best = 历史最高。若 current + nums[i] 不如 nums[i]，说明前缀拖后腿，从 i 重新起跑。每一次更新都必须保持核心不变量，而不是只让样例碰巧得到正确答案。

1func maxSubArray(nums []int) int {
2    current := nums[0]
3    best := nums[0]
4
5    for i := 1; i < len(nums); i++ {
6        if current + nums[i] < nums[i] {
7            current = nums[i]
8        } else {
9            current = current + nums[i]
10        }
11
12        if current > best {
13            best = current
14        }
15    }
16
17    return best
18}

1. 1题目与输入正数 = 能量果实，负数 = 荆棘陷阱。找出一段连续旅程，使总体力收益最高。 因为：current = 当前连续冲刺段的能量；best = 历史最高。若 current + nums[i] 不如 nums[i]，说明前缀拖后腿，从 i 重新起跑。
2. 2从第一格出发第一个元素同时初始化 current 与 best。 因为：全负数时也不能把初值设成 0。
3. 3预测下一步先不要看下一帧——根据当前不变量,预测算法接下来会怎么动。 因为：主动预测会暴露你对不变量的真实理解,比被动看动画有效得多。
4. 4i=3 · 从 +4 重新出发负贡献前缀被丢弃，小狐狸从当前砖块重新出发。 因为：best 记录历史最高，current 下降不会抹掉 best。
5. 5i=4 · 带着 +4 继续走前面段仍有贡献，继续延伸旅程。 因为：current 只描述以 i 结尾的最优，best 保持历史峰值。
6. 6i=6 · 刷新 best = 6前面段仍有贡献，继续延伸旅程。 因为：best 记录历史最高，current 下降不会抹掉 best。
7. 7i=8 · current 回升，best 仍是 6前面段仍有贡献，继续延伸旅程。 因为：current 只描述以 i 结尾的最优，best 保持历史峰值。
8. 8收尾与复杂度bestSum = 6，bestSegment = [4,-1,2,1]。 因为：时间 O(n) · 空间 O(1)。current = 当前连续冲刺段的能量；best = 历史最高。若 current + nums[i] 不如 nums[i]，说明前缀拖后腿，从 i 重新起跑。

1func maxSubArray(nums []int) int {
2    current := nums[0]
3    best := nums[0]
4
5    for i := 1; i < len(nums); i++ {
6        if current + nums[i] < nums[i] {
7            current = nums[i]
8        } else {
9            current = current + nums[i]
10        }
11
12        if current > best {
13            best = current
14        }
15    }
16
17    return best
18}

代码窗口不会按容易漂移的固定数字行号硬绑动画，而是根据当前语义阶段， 在完整 Go 实现中定位选择、计算、写回或返回分支。当前变量与高亮行一起变化。

1func maxSubArray(nums []int) int {
2    current := nums[0]
3    best := nums[0]
4
5    for i := 1; i < len(nums); i++ {
6        if current + nums[i] < nums[i] {
7            current = nums[i]
8        } else {
9            current = current + nums[i]
10        }
11
12        if current > best {
13            best = current
14        }
15    }
16
17    return best
18}

// 解法一 DP
func maxSubArray(nums []int) int {
	if len(nums) == 0 {
		return 0
	}
	if len(nums) == 1 {
		return nums[0]
	}
	dp, res := make([]int, len(nums)), nums[0]
	dp[0] = nums[0]
	for i := 1; i < len(nums); i++ {
		if dp[i-1] > 0 {
			dp[i] = nums[i] + dp[i-1]
		} else {
			dp[i] = nums[i]
		}
		res = max(res, dp[i])
	}
	return res
}

// 解法二 模拟
func maxSubArray1(nums []int) int {
	if len(nums) == 1 {
		return nums[0]
	}
	maxSum, res, p := nums[0], 0, 0
	for p < len(nums) {
		res += nums[p]
		if res > maxSum {
			maxSum = res
		}
		if res < 0 {
			res = 0
		}
		p++
	}
	return maxSum
}

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

func main() {
    // 1. 主例
    //    输入：mode="max-subarray", nums=[-2,1,-3,4,-1,2,1,-5,4]
    //    期望：bestSum = 6，bestSegment = [4,-1,2,1]。
    //
    // 2. 失败 / 未命中
    //    检查：全负数时 cur 也要 max(a[i],...),初值不能设 0。
    //
    // 3. 边界
    //    空输入、单元素、最小合法规模，以及答案恰好落在边界的情况。
    //
    // 4. 迁移
    //    LC152 乘积子数组；LC121 股票
}

Go 参考实现基于 halfrost/LeetCode-Go 的 MIT 许可代码整理，并按本站教学结构补充解释与动画映射。

1. 1题意正数 = 能量果实，负数 = 荆棘陷阱。找出一段连续旅程，使总体力收益最高。
2. 2重复直接递归会反复求同一个子问题；动态规划把答案写入状态表并按依赖顺序复用。
3. 3优化current = 当前连续冲刺段的能量；best = 历史最高。若 current + nums[i] 不如 nums[i]，说明前缀拖后腿，从 i 重新起跑。
4. 4证明cur 只关心以 i 结尾的最优,负贡献前缀被丢弃。
5. 5复杂度时间 O(n)，空间 O(1)