小狐狸能量森林冒险

可视化:能量森林冒险

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

小狐狸沿着森林连续地砖前进——正数补体力，负数是陷阱，找出体力收益最大的一段路。

时间 O(n)空间 O(1)Best Sum = 6

题目1 / 14

萤火路径 · current金色藤蔓 · best果实陷阱

-2i=0

+1i=1

-3i=2

+4i=3

-1i=4

+2i=5

+1i=6

-5i=7

+4i=8

森林地砖已就绪，小狐狸即将出发

小狐狸能量森林冒险

小狐狸沿着森林中的连续地砖前进，正数补体力，负数是陷阱，要找体力收益最大的一段路。

Kadane：在 nums 中找和最大的连续子数组，每步比较 extend vs restart。

冒险 HUD

当前格 i · nums[i]

0 · -2

决策

初始化

current · 萤火路径-2

best · 金色藤蔓-2

当前段 → —

最佳段 → —

CodeTrace · Go · Kadane

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}

本步讲解 · 题目与输入

当前发生了什么

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

为什么正确

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

面试怎么说

Kadane O(n):cur=max(nums[i],cur+nums[i]),ans=max(ans,cur)。