galahadv2 最近的时间轴更新
galahadv2

galahadv2

V2EX 第 414505 号会员,加入于 2019-05-22 09:24:19 +08:00
galahadv2 最近回复了
1. 学好线性代数;
2. 学好算法和数据结构;
3. 学好英语;
4. 多写代码;
5. 多读几本计算机经典书籍。
《算法导论》 4.1 讲解了如何使用分治法求解最大子数组的问题,在练习题 4.1-5,提示了一个线性时间的算法。

对于数组 A, 如果已经知道了 A[0:j] 的最大子数组,那么可以按如下性质扩展得到 A[0:j+1] 的最大子数组:
```
A[0:j+1] 的最大子数组要么依然是 A[0:j] 的最大子数组,要么是某个子数组 A[i:j+1] (1<=i<=j+1>>)
```

上面这句话也可以直观地理解为:
```
A[0:j+1] 的最大子数组只有有两种可能情形:

1. 依然是 A[0:j] 的最大子数组,它必定不包含 A[j] 这个元素(注意 a[j] 是 A[0:j+1] 的最后一个元素,并不包含在 A[0:j]中);
2. 是一个位于最右边的子数组(A[i:j+1] 形式的)。
```
因此在循环体中,每次都计算一下情形 2 的最大子数组,即计算必定包含最后一个元素的最大子数组(我们给它命名为最右最大子数组),然后和 A[0:j]相比较,较大的即为 A[0:j+1]的最大子数组。

``` golang
func maxIncludeRight(a []int) int {
sum := 0
max := math.MinInt64
for i := len(a) - 1; i >= 0; i-- {
if sum += a[i]; sum >= max {
max = sum
}
}
return max
}

func maxSubArray(nums []int) int {
max := nums[0]
for i := range nums {
if right := maxIncludeRight(nums[:i+1]); max < right {
max = right
}
}
return max
}
```

上面的代码已经可以正常工作了,现在来观察一下是否还有优化的余地。

观察 maxIncludeRight ,每次它都全新地来计算“最大最右子数组”,实际上,如果我们已知 a[0:i]的“最右最大子数组”,那么可以很快求出 a[0:i+1]的“最大最右子数组”。方法如下:

1. 如果 a[0:i]的最右最大子数组 m 小于 0,则 a[0:i+1]的最右最大子数组就是 a[i];
2. 如果 a[0:i]的最右最大子数组 m 不小于 0,则 a[0:i+1]的最右最大子数组就是 m+a[i]。

初始时,a[0:1]的最右最大子数组为 a[0], 这样可以一步步来求出 a[0:i]的最右最大子数组了。代码如下:

``` golang
func maxIncludeRight(a []int, i int) int {
max := a[0]
for _, v := range a[1 : i+1] {
if max < 0 {
max = v
} else {
max += v
}
}
return max
}

func maxSubArray(nums []int) int {
max := nums[0]
for i := range nums {
if right := maxIncludeRight(nums, i); max < right {
max = right
}
}
return max
}
```

注意到两次循环可以合并,一次搞定,因此最终的代码如下:

```go
func maxSubArray(nums []int) int {
max, sum := nums[0], nums[0]
for _, e := range nums[1:] {
if sum < 0 {
sum = e
} else {
sum += e
}
if sum >= max {
max = sum
}
}
return max
}
```

最后阅读上面这段代码,也可以换个角度来思考最大子数组问题。

最大子数组必定满足这一性质:
```
位于它左侧的任何一个子数组必定大于 0
```

因为如果存在一个小于 0 的左侧子数组,则可以去掉它,而得到一个新的最大子数组。

例如,对于[-2, 1, -3, 4, -1, 2, 1, -5, 4]:
[-2, 1, -3]肯定不是最大子数组,因为左侧的 [-2, 1]小于 0
从 4 开始往右,
[4]
[4,-1]
[4, -1, 2]
[4, -1, 2, 1]
以上都有可能是最大子数组。

[4, -1, 2, 1,-5] 不可能是最大子数组,因为它小于 0。

因此,按此方法从左向右,舍弃所有已知左侧子数组小于 0 的情形,然后取最大值即可。
关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   2844 人在线   最高记录 6543   ·     Select Language
创意工作者们的社区
World is powered by solitude
VERSION: 3.9.8.5 · 13ms · UTC 15:22 · PVG 23:22 · LAX 08:22 · JFK 11:22
Developed with CodeLauncher
♥ Do have faith in what you're doing.