谈最大子段和问题的三种解题策略.doc

《谈最大子段和问题的三种解题策略.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、最大子段和问题的不同策略分析与实现(湖北省襄阳市第五中学杨兵)最大子段和问题描述：给定由N个整数（可能为负整数）组成的序列a1，a2，…，an，求该序列形如的子段和的最大值。当所有整数均为负整数时定义其最大子段和为0。例如当（a1，a2，…，a6）=（-2，11，-4，13，-5，-2）时最大子段和为20，即a2，a3，a4序列为最大子段。下面我们来探讨一下解决这一问题的三种不同策略。一、枚举策略这种策略是我们最容易想到的，依照最大子段和的定义，不难理解所求最大子段和为max{0，max(其中1≤i≤j≤n)}，因此我们只需枚举所有的i和j即

2、可求出序列的最大的子段和。主要代码如下，其中a[i]表示ai。proceduremaxsum(VARmax:longint);vari,j:integer;thissum:longint;beginmax:=0;fori:=1tondobeginthissum:=0;forj:=itondobeginthissum:=thissum+a[j];ifmax

3、行改进。从问题解的结构可以看出，它适合于分治算法求解。如果将所给的序列a1，a2，…，an分为长度相等的两段序列a1，a2，…，a(ndiv2)和a(ndiv2+1)，a(ndiv2+2)，…，an，分别求出这两段的最大子段和，则a1，a2，…，an的最大子段和有三种可能：1．a1，a2，…，an的最大子段在前半段，即序列a1，a2，…，an的最大子段和与a1，a2，…，a(ndiv2)序列的最大子段和相等。2．a1，a2，…，an的最大子段在后半段，即序列a1，a2，…，an的最大子段和与a(ndiv2+1)，a(ndiv2+2)，…，an

4、序列的最大子段和相等。3．a1，a2，…，an的最大子段的段首元素在前半段，段尾元素在后半段，即a(ndiv2)和a(ndiv2+1)都在最大子段内。对于第一和第二种情形，我们可以由递归求得，对于第三种情形，我们可以先在前半段求出以a(ndiv2)为尾的最大子段和S1，再在后半段求出以a(ndiv2+1)为首的最大子段和S2，则S1+S2即为第三种情形的最大子段和。主要代码如下，其中a[i]表示ai。proceduremaxsum(x,y:integer;varmax:longint);varcenter,i:integer;s1,s2,le

5、fts,rights,leftmax,rightmax:longint;beginifx=ythenbeginifa[x]<0thenmax:=0elsemax:=a[x];endelsebegincenter:=(x+y)div2;maxsum(x,center,leftmax);maxsum(center+1,y,rightmax);s1:=0;lefts:=0;fori:=centerdowntoxdobeginlefts:=lefts+a[i];ifs1

6、ori:=center+1toydobeginrights:=rights+a[i];ifs20时，b[j]=b[j-1]+a[j]，否则b[j]=a[j]，明显具有最优子结构和无后效性，适宜用动态规划来解决。由此可得

7、状态转移方程：b[j]=max{b[j-1]+a[j]，a[j]}，临界状态：如果a[1]≥0，b[1]=a[1]，否则b[1]=0，最终所求就是。主要代码如下，其中a[i]表示ai。proceduremaxsum(varmax:longint);varb:array[1..30000]oflongint;i:integer;begifa[1]<0thenb[1]:=0elseb[1]:=a[1];max:=b[1];fori:=2tondobeginifb[i-1]>=0thenb[i]:=b[i-1]+a[i]elseb[i]:=a[i]

8、;ifmax