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

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

2、edure maxsum(VAR max:longint); var i,j:integer; thissum:longint; begin max:=0; for i:=1 to n do begin thissum:=0; for j:=i to n do begin thissum:=thissum+aj; if maxthissum then max:=thissum; end; end; end;此算法的时间复杂度为O(n2)。二、 分治策略针对最大子段和这个具体问题本身结构，我们还可以从算法设计策略上对上述算法进行改进。从问题解的结构可以看出，它适合于分治算法求解。如果将所给的序列

3、a1，a2，an分为长度相等的两段序列a1，a2，a(n div 2) 和a(n div 2+1)，a(n div 2+2)，an，分别求出这两段的最大子段和，则a1，a2，an的最大子段和有三种可能：1a1，a2，an的最大子段在前半段，即序列a1，a2，an的最大子段和与a1，a2，a(n div 2) 序列的最大子段和相等。2a1，a2，an的最大子段在后半段，即序列a1，a2，an的最大子段和与a(n div 2+1)，a(n div 2+2)，an 序列的最大子段和相等。3a1，a2，an的最大子段的段首元素在前半段，段尾元素在后半段，即a(n div 2)和a(n div 2+1)

4、都在最大子段内。对于第一和第二种情形，我们可以由递归求得，对于第三种情形，我们可以先在前半段求出以a(n div 2)为尾的最大子段和S1，再在后半段求出以a(n div 2+1)为首的最大子段和S2，则S1+S2即为第三种情形的最大子段和。主要代码如下，其中ai表示ai。procedure maxsum(x,y:integer;var max:longint); var center,i:integer; s1,s2,lefts,rights,leftmax,rightmax:longint; begin if x=y then begin if ax0 then max:=0 else m

5、ax:=ax; end else begin center:=(x+y) div 2; maxsum(x,center,leftmax); maxsum(center+1,y,rightmax); s1:=0; lefts:=0; for i:=center downto x do begin lefts:=lefts+ai; if s1lefts then s1:=lefts; end; s2:=0; rights:=0; for i:=center+1 to y do begin rights:=rights+ai; if s2rights then s2:=rights; end; ma

6、x:=s1+s2; if maxleftmax then max:=leftmax; if max0时，bj=bj-1+aj，否则bj=aj，明显具有最优子结构和无后效性，适宜用动态规划来解决。由此可得状态转移方程：bj=maxbj-1+aj，aj，临界状态：如果a10，b1=a1，否则b1=0，最终所求就是 。主要代码如下，其中ai表示ai。 procedure maxsum(var max:longint); var b:array1.30000 of longint; i:integer; beg if a1=0 then bi:=bi-1+ai else bi:=ai; if maxbi then max:=bi; end; end; 此算