动态规划法求解最大连续子序列和问题

张玮

摘要

最大连续子序列和问题是一个经典问题，有多种求解方法，每种方法的时间复杂度大不一样，用动态规划法求解该问题的时间复杂度为0（n），是所有方法中时间效率最优的。本文详细阐述了用动态规划法求解最大连续子序列和问题的整个分析过程，介绍了动态规划法求解问题的特点，最后给出了算法的实现代码和解释。

【关键词】动态规划 最大连续子序列和

1 引言

动态规划法是解决最优化问题的一种常用方法，其基本方法是将欲求解的问题划分为规模更小的子问题，原问题的解蕴含在子问题的最优解中。用动态规划法求解的问题，通常情况下其子问题会相互重叠，因此通常采用自底向上的迭代求解方法，并在计算过程中记录下每一个子问题的解，以便于重复使用。动态规划法是一种求解问题的思想，没有固定的公式，针对不同的问题都有特定的算法。

最大连续子序列和问题描述如下：给定一个序列A={a₁，a₂，a₃，….a_n}，求该序列的一个连续子序列{a_i，a_i+1，…，a_j-1，a_j}，其中1≤i≤j≤n，使得该子序列的和为最大。对于该问题，求解算法有多种，最坏的方法是枚举所有可能子序列，从中找出和为最大的序列，这种方法时间复杂度为O（n³）。用动态规划法求解该问题的时间复杂度为O（n）。下面就如何用动态规划法的求解该问题做详细阐述。

2 问题分析与算法推导

动态规划法的求解问题的基本方法是将原问题分为若干个阶段，由前一阶段的最优解求出下一阶段的最优解。用动态规划法解决问题，需要找出各阶段之间的联系，即由一个阶段发展为另一个阶段的状态转移方程。对原问题阶段的划分应满足最优性原理。最大连续子序列和问题用动态规划法求解，关键在于子问题（阶段）的划分和状态转移方程的建立。

假设有整数序列Qn={q₁，q₂，q₃，……q_n-1，q_n}，要求找出Q_n的最大连续子序列和。不妨假设Q_n的最大连续子序列和对应的子序列为q_k，q_k+1，….，q_w，其中1≤k≤w≤n，显然k和w的取值可能是1到n中的任何值，或者说Q_n的最大连续子序列和必然是以某个q_w（1≤w≤n）元素结尾的连续子序列的和，不妨假设S_k（1≤k≤n）代表Q_n中以q_k为结尾的最大连续子序列和，则求Q_n最大连续子序列和问题转化为找最大的S_k的问题。怎样求s_k？按照动态规划法应该找出从一个阶段向下一个阶段演进的状态转移方程，既找出S_k-1和S_k的关系。显然有S₁=q₁，S2和S1之间存在什么样的关系呢？如果q₁+q₂=q₂，则S₂=S₁+q₂;若q₁+q₂≤q₂，那S₂=q₂，由此推导出：

①式中2≤k≤n。对①式可以用归纳法简单证明。

结合公式①对于Qn中以元素q_k（k≥1）为结尾的最大连续子序列和求解方程如下：

公式②即为求S_k的状态转移方程。Q_n的最大连续子序列和为max（S₁，S₂，S₃，……，S_n-1，S_n）。

3 算法实现

下面给出按照公式②设计的C语言源代码。

[算法]求序列a的最大连续子序列和并输出该子序列

void maxSubAxray（int a[]，int n）{//a为要求解的序列，n为序列长度

int*s=（int*）malloc（n*sizeof（int））;//存储以每个元素结尾的最大连续子序列和

int*start=（int*）malloc（n*sizeof（int））;//存储每个最大连续子序列对应的起始位置

int i，max=0;//max记录最大连续子序列和的序列结尾元素的位置

for（i=0;i

//依次求出每个元素结尾的最大连续子序列和，及其对应的起始元素位置for（i=1;i

if（s[i-1]+a[i]>a[i]）{s[i]=s[i-1]+a[i];start[i]=start[i-1]：}

}

for（i=0;i<10;i++）{//找出原问题的最大连续子序列和对应序列的结尾元素位置

if（s[max]

}

//输出最大连续子序列和及其对应的子序列

printf（"＼n最大连续子序列和是：%d＼n"，s[max]）;

printf（"对应的连续子序列是："）;

for（i=start[max];i<=max;i++）printf（"%d"，a[i]）;

free（s）;

free（start）;

}

4 結语

动态规划法求解问题的关键在于如何将原问题合理地划分为多个相似的子问题以减小问题的规模。就本文所论述的最大连续子序列和问题而言，用动态规划法解决的关键就在于如何观察到原问题实际上是寻找以某个元素为结尾的一个连续子序列。通常情况下，在实际应用中不同的问题用动态规划法求解的具体算法是不同的，需要根据问题的特点做细致的分析，合理划分阶段，建立正确的状态转移方程。

参考文献

[1]（美）Thomas H.Cormen等著，殷建平等译.算法导论（第3版）[M].机械工业出版社，2016.

[2]刘雄辉等.动态规划思想在ACM竞赛中的应用研究[J].电脑知识与技术：学术交流，2017（6X）：238-239.