动态规划之最大子段和

去年有想过将研究过的动态规划总结一下，不过那时没有写博客习惯，后来就不了了之了。这次不作大而无望的总结了，有一点说一点。

以下部分代码和分析出自《计算机算法设计与分析》（王晓东编著）。

（一）最大子段和问题

最大子段和问题复杂度为O(n)的解法，在上篇博客

最大连续子序列

中已经谈过了。这里在稍微提及一下，主要是更形式化的说明为什么是用动态规划。然后谈一下这个问题的分治解法。

设所要求的序列为
$a_1,a_2,\cdots,a_n$
，记：

$b[j]=max_{1 \le i \le j}{\sum_{k=i}^ja[k]},1\le j \le n$

也就是说：

$b[1] = a[1] \\ b[2] = max\{a[1]+a[2], a[2]\} \\ b[3] = max\{a[1]+a[2]+a[3], a[2]+a[3], a[3]\}$

那么原问题转化为：

$max_{1 \le i \le j \le n}\sum_{k=i}^ja[k]\\ =max_{1\le j \le n}max_{1 \le i \le j}\sum_{k=i}^ja[k]\\ =max_{1 \le j \le n}b[j]$

而数组b是可以递归表达的，如下：

$b[j] = max\{b[j-1]+a[j], a[j]\}, 1 \le j \le n$

或者表示为：

$b[j] = \left\{\begin{matrix} b[j-1]+a[j] & ,b[j-1]>0\\ a[j] & ,otherwise \end{matrix}\right., 1\le j \le n$

这样就很明显的显示出了最优子结构性质。

具体算法就不给了，上篇博客已经给出了。