寻找序列中的最大值及其相关结构--探索最大值问题

最大和子序列

这个问题的起始阶段表现得相当原始：对于一个给定的序列，请从中提取出一段连续且非空的部分，并使这一部分的总和达到最大值 。下面列举了几种常见的解决方法

1、穷举法

逐一计算序列中每一个子区间的累加值，并对各子区间之和进行比较以确定最大总值对应的区间。

2、分治法

给定序列{a_i : i = 1,2,…,n}中，在确定中间位置的基础上将该序列划分为两个区间：左边区间定义为i=1到i=n/2的部分（记为left），右边区间定义为i=n/2+1到i=n的部分（记为right）。根据这一划分方法，则该数组的最大子数组可能具有以下三种分布形式：其一是在左半部分完全包含的最大子数组、或者是在右半部分完全包含的最大子数组、或者是在跨越左右两部分的最长连续元素组合。对于上述三种可能性分别计算对应的最优值之后再进行比较，则可得出原始数据中的最大子数组之和。

3、动态规划

通过动态规划方法来解决这一问题的核心步骤就是确定状态转移方程。考虑序列{a[i]}（其中i取值于整数范围），其中我们定义最大字段和函数为：

\text{MaxSubarray}[m] = \text{Max}\left\{\sum_{i=1}^{m} a[i]\right\}

即计算从第一个元素到第m个元素的最大字段和。根据MaxSubarray[