最大子段和问题的算法分析与比较

陈坚强

摘要：随着经济的发展、社会的进步和科学研究的深入，要求用计算机解决的问题越来越复杂，规模越来越大。对求解这类问题的算法进行分析具有特别重要的意义，下面通过分别使用分治法和动态规划法来求解最大子段和问题，并分析算法的优劣。

关键词：最大子段和；分治法；动态规划法；时间复杂度

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2015）27-0163-01

1 最大子段和

给定由n个整数（可能为负整数）组成的序列a1，a2，a3…，an，求该序列形如∑ak（k=i，i+1…j）的子段和最大值。当所有的整数均为负整数时定义其最大子段和为0。依次定义，所求的最优值为

2 分治法求解最大子段和问题

針对最大子段和这个具体问题本身的结构，从问题的本身的解的结构可以看出，它适合于用分治法求解。如果将所给的序列a[1：n]分为长度相等的两段a[1：n/2]和a[n/2+1：n]，分别求出这两段的最大子段和，则a[1：n]的最大子段和有三种情况：

（1）a[1：n]的最大子段和与a[1：n/2]的最大子段和相同；

（2）a[1：n]的最大子段和与a[n/2+1：n]的最大子段和相同；

（3）a[1：n]的最大子段和的起始位置在前半段，终止位置在后半段。

对于（1），（2）情况，我们可以按递归方法求得。对于情况（3）容易看出a[n/2]与a[n/2+1]在最优子序列中。因此，我们可以在a[1：n/2]中计算出s1=max∑a[k]（k=i，i+1，…n/2）其中1<=i<=n/2，并在a[n/2+1：n]中算得s2=max∑a[k]（k=n/2+1…i）（n/2+1<=i<=n），则s1+s2即为（3）最优值。

4 结论

由上面的分析可知，分治算法时间复杂度为O（nlogn），而动态规划算法的时间复杂度为O（n）。可见动态规划算法其效率较高，算法较优。相同点：分治法和动态规划法都需要问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质。不同点：分治法的问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。而动态规划法的问题所分解出的各个子问题具有重叠性质，即子问题之间有包含公共的子问题。

参考文献：

[1] 周波，刘文强，乔付，等.算法设计与分析课程中最大子段和问题的教学探讨[J].中国教育技术装备，2013（27）.

[2] 袁佳乐. 浅析求解最大子段和问题的算法[J].西安文理学院学报，2009（3）.

[3] 王晓东.计算机算法设计与分析[M].电子工业出版社，2001.

[4] 王能超.数值分析简明教程[M].高等教育出版社，2003.

[5] 廖慧芬，邵小兵. 动态规划算法的原理及应用[J]. 中国科技信息，2005（21）.

[6] 廖作斌. 一种改进的最大m子段和算法设计[J]. 湖北科技学院学报，2014（03）.

[7] 廖作斌. 高校计算机专业高级语言程序设计课程的教学改革[J].宜春学院学报，2010（4）.

[8] 王荣海，曾玉珠，廖作斌.基于集中形式的软件工程课程设计[J].计算机教育，2010（17）.

[9] 廖慧芬，邵小兵. 动态规划算法的原理及应用[J].中国科技信息，2005（21）.