最大子段和 | 最大子矩阵 | 最大M子段和

admin

最大子段和
给定由n个整数（可能为负整数）组成的序列as = a0, a1, ... , a(n - 1)，求该序列形如∑ak(k = l => r - 1)的子段和的最大值。对于全是负数的数组最大子段和为0。

简单方法
给定这个题目，首先可以想到枚举每一对可能的左右边界[l, r)并计算其中的和sum[l, r)，这样一个方法可以实现O(n ^ 3)的算法。

观察到这之中的重复计算，我们可以预处理一下，建立一个数组，其中存放所有的sum[0, r)，计算sum[l, r)时利用sum[l, r) = sum[1, r) - sum[1, l)，这样可以将算法优化到O(n ^ 2)。（典型的空间换时间）

进一步分析
优化的重要思路是利用先前的计算（上面的预处理数组是这一思想的极致），对于最优化问题，自然是思考如何利用子最优构造最优，也就是寻找最优子结构。

如果有最优解在区间[l, r)。那么，对于l <= m <= r，我们可以发现sum[l, m) >= 0。否则，sum[m, r) >= sum[l, r)。同理：sum[m, r) >= 0。

反之，对于任意1 <= m <= r,[l, m)的最优前缀和[m, r)的最优后缀构成bst[l, r)。（最优子结构）

现在有原问题求bst[l, r)，对于任意l < m < r，我们可以分解问题为

bst[l, r) = max(bst[l, m), bst[m, r), [l, m)中的最优后缀+[m, r)中的最优前缀)
上面惊现了标准的分治法，不过看上去非常复杂，我们要找到子解的最优，同时维持两端最优信息……

仔细看看，这是因为m可以是(l, r)中的任意位置，如果把m选在r - 1，就有

bst[l, r) = max(bst[l, r - 1), [l， r - 1)中的最优后缀+a[r - 1])
这个递推公式最重要的优化是将l排除出了计算过程，也就是说求bst[l, r)是r的变化过程，l是“常数”，有

bst(r) = max(bst(r - 1), maxSuffix(r - 1) + a[r - 1])
这个公式中的变量r是线性变化的，不过maxSuffix情况如何还没分析。

通过上面的讨论我们知道，maxSuffix(r) >= 0

maxSuffix(r) = max(0, maxSuffix(r - 1) + a[r - 1])
汇总
maxSuffix(r) = 0                                    r = 0
maxSuffix(r) = max(0, maxSuffix(r - 1) + a[r - 1])    r > 0

bst(r) = 0                                            r = 0
bst(r) = max(bst(r - 1), maxSuffix(r))                r > 0
整理思路
可以重述上面的思路：

我们取每一个右端点r，计算最优后缀，其中的最大值即为最大和子区间
最优后缀masSuffix(r)可以通过maxSuffix(r - 1)在常数时间算出
算法的复杂度为O(n)
最重要的：算法的递推不是建立在最优值观点上的，而是最优后缀上的，虽然两者的值相同。

二维推广：最大子矩阵
二维上的最大和子区域可以直接转化为一维问题。

在列上枚举[l, r),将zip[i] = sum(m[i][k]) (l <= k < r)看成是一个数列，就可以像上面那样对zip求解了。

复杂度：O(a * b ^ 2)

多子段推广：最大M子段和
给定as[0, n)和正整数m，求m个不相交的子段，使m个子段的总和最大。

直接从递推出发

定义

dp[i][j] : 表示as[0, j)的i字段和
oneSum[l, r) : 表示[l, r)上的最大单字段和
有

dp[i][j] = max(dp[i - 1][k] + oneSum[k, j)) (i <= k < j)
通过上述递推式可以写出一个O(n ^ 4)时间的算法。

观察可以发现oneSum上的O(n)不是很必要，对于固定的l，可以打出整张oneSum[l, r)表：每次固定一个l，O(n)时间打出[l, r)，总时间消耗O(n ^ 2)。

现在可以在O(n ^ 3)时间内求解了，不过还可以继续优化。

接下来的优化比较复杂：仔细观察上面的递推式，可以发现对于同一个i，j的求值是没有相互关联的。这给了我们一个信号，我们能否发现j们的相互关系？

视线回到上方“整理思路”的部分，当时我们通过转换视角建立了递推方程。这里呢？

对于固定的i，我们希望通过递推的方式求出j，即[j-x] → [j]

考虑dp[i][j]和dp[i][j - 1]的关系，借鉴一维时的思路，我们有

temp[j] = max(dp[i - 1][k]) (k <= j)

dp[i][j] = max(temp[j - 1], dp[i][j - 1]) + as[j - 1]
temp[j - 1] : 表示取dp[i - 1][k < j]中最优的做前i - 1段，第i段从j处另起

dp[i][j - 1] : 表示继承dp[i][j - 1]流传下来的第i段

temp[j]可在计算dp[i - 1]时计算，不增加复杂度

这里我一开始的思路里并没有引入temp表，而是希望通过dp[i - 1][j - 1]来表示dp[i - 1]段最优子解，不过后来发觉dp[i - 1][j - 1]不一定具有temp[j - 1]的最优性，而且还无法表示跳跃（相邻两段之间有没有纳入子段中的部分）。才回头看书上的步骤。

回头看，这一递推式的思路与maxSuffix是何其相似。

admin

https://www.cnblogs.com/hbhszxyb/p/13130933.html