求教各位 v 站大佬， [最大子数组] 这道题是否可进行优化？（望轻喷）

[qawsed2019]

描述

给定一个整数数组和一个整数 k，找出 k 个不重叠子数组使得它们的和最大。每个子数组的数字在数组中的位置应该是连续的。返回最大的和。

样例 1

输入: 
List = [1,2,3]
k = 1
输出: 6
说明: 1 + 2 + 3 = 6

样例 2

输入:
List = [-1,4,-2,3,-2,3]
k = 2
输出: 8
说明: 4 + (3 + -2 + 3) = 8

先说一下我的解题思路： 首先预处理前缀和，使 sum[i]代表以第 i 个数结尾的长度为 k 的子串和，方便计算区间的和。然后对三段的起始位置进行遍历，求和，时间复杂度是 O(n^3)。那么，如何优化呢？大家有没有建议？ 请各位 v 站大佬轻喷（＞人＜；）

[littlekui]

评价你的解题思路：我只看懂了前缀和，之后的每个字都不知道你在说啥。。

如果想要这道题的解答，可以参考下 Lintcode 上： https://www.lintcode.com/problem/maximum-subarray-iii/description#utm_source=v2exmn

[ZSeptember]

这个？

[geelaw]

很经典的动态规划问题，考虑 f(i, j) 表示前 i 个数拿 j 段且第 i 个数选中时能得到的最大和，g 则表示第 i 个数不选的情况，那么

f(i, j) = max{ f(i-1, j) + a[i-1], g(i-1, j-1) + a[i-1] }
g(i, j) = max{ f(i-1, j), g(i-1, j) }

f(?, 0) = -infty
g(?, 0) = 0

答案 = max{ f(n, k), g(n, k) }

令第一维滚动，可以得到 streaming 的算法，时间 O(nk)，空间 O(k)。

[geelaw]

@geelaw #3 Oops 状态转移的时候应该考虑两个相邻的段实际上是接起来的，一种方法是答案改成 max{ f(n, j), g(n, j) } over j<=k，另一种是虚拟地在中间插入 0。

[galahadv2]

《算法导论》 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 的情形，然后取最大值即可。

[qawsed2019]

@ZSeptember 是否发了图片？貌似木有显示诶

[qawsed2019]

@galahadv2 多谢~~~

[qawsed2019]

@galahadv2 三克油，(>▽<)

[jxf2008]

```
for(int i = 0 ; i < k ; ++i)
```

[jxf2008]

发错。。。。不好意思

[qawsed2019]

@jxf2008 啊咧(o_ _)ﾉ

[qawsed2019]

@jxf2008 是不是故意来调戏的(lll ￢ω￢)

[ZSeptember]

@qawsed2019 无视吧，看错题目了。