资源描述：
《最大子序列和的总结.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
1、最大子序列和第一种情况：可以一个不取【问题描述】：最大子序列和也叫数列的连续最大和，顾名思义，就是在一个长度为n的数列{An}中，求i，j（1<=i<=j<=n），使得数列{An}中，第i个元素到第j个元素之间，所有元素的和最大。例如：-2,11,-4,13,-5,-2时答案为20（11-413）解法一穷举法：以前我想出了一种算法，具体做法是：取出所给序列的所有子序列求和,共分n组，第一组长度为1，有n个；第二组长度为2,有n-1个；……，最后一组，长度为n,只有一个。比较这n(n＋1)/2个序列的和，再将每组的最大值比较，从而得到最大值以及其上下标。a1
2、 a2 an-1 ana1+a2 a2+a3 an-1+an a1+a2+a3 a2+a3+a4 ...... ...... ......a1+a2......+an-1 a2+a3......+ana1+a2......+an-1 +an此算法比较直接，也容易写出代码，但其时间开销为O(n2)，空
3、间开销为O(n)，效率不高。解法二：动态规划求解，1、样例求解过程：123456A[i]-211-413-5-2F[i]01172015132、动态规划方程为：F[i]：表示以元素i结尾的连续最大子序列的和那么对于第i个元素来说，要形成连续的最大子序列，只和相邻的前一个元素有关。因为可以不取，所以如果元素a[i]连接到以元素i-1结尾的最大连续子序列f[i-1]后是负数（f[i-1]+a[i]<0）;则宁可不取，这样最大连续子序列和为0。动态方程：f[i]:=max{0,f[I-1]+a[i]}(边界条件：f[0]=0;)3、代码1：forI:=1tondoi
4、f(f[I-1]+a[i])>0thenf[i]:=f[I-1]+a[i]elsef[i]:=0;max:=-maxlongint;fori:=1tondoiff[i]>maxthenmax:=f[i];程序代码二：迭代进行best:=-maxlongint;temp:=0;for i:=1 to n do begin temp:=temp+a[i]); if temp>best then best:=temp; if temp<0 then temp:=0; end;注意：加粗的循环体部分的顺序万万不可颠倒！第二种情况：一定要取一个
5、。1、解法一：动态规划求解，2、样例求解过程：123456A[i]-349-2-58F[i]-3初始化一个4=max（-3+4，4）13=max{4+9,9}11=Max{13-2,-2}6=max{11-5,-5}14=Max{6+8,8}1、动态规划方程为：F[i]：表示以元素i结尾的至少要取一个的连续最大子序列的和那么对于第i个元素来说，有两种选择：选择一：因至少要选一个，所以可单独选a[i],此时和为a[i];选择二：把a[i]连接到第i-1个元素结尾的最大连续子序列后。此时和为f[i-1]+a[i];两种情况选较大者。所以动态方程：f[i]:=max
6、{a[i],f[I-1]+a[i]}(边界条件：f[1]=a[1];)2、代码：F[1]:=a[1];forI:=2tondoif(f[I-1]+a[i])>a[i]thenf[i]:=f[I-1]+a[i]elsef[i]:=a[i];max:=-maxlongint;fori:=1tondoiff[i]>maxthenmax:=f[i];第三种情况：至少要取两个。1、解法一：动态规划求解，2、样例求解过程：123456A[i]-349-2-58F[i]-3只能取一个-3+4=1取两个13=max{4+9,9+1}11=Max{9-2,13-2}6=max{
7、-2-5,11-5}14=Max{-5+8,6+8}说明：以第4个元素为例：选择一：取长度为2：9-2=7；选择二：把元素a[4]连接到元素a[3]结尾的后面。F[3]+a[4]=13-2两者最较大者。3、动态规划方程为：F[i]：表示以元素i结尾的至少要取两个的连续最大子序列的和那么对于第i个元素来说，有两种选择：选择一：因至少要选两个，所以和为a[i-1]+a[i];选择二：把a[i]连接到a[i-1]元素结尾的长度至少为2的最大连续子序列后。此时和为f[i-1]+a[i];两种情况选较大者。所以动态方程：f[i]:=max{a[i-1]+a[i],f[I
8、-1]+a[i]}(i>=3)(边界条
