最大子序列和的总结.doc

最大子序列和第一种情况：可以一个不取【问题描述】：最大子序列和也叫数列的连续最大和，顾名思义，就是在一个长度为n的数列An中，求i，j（1=i=j=n），使得数列An中，第i个元素到第j个元素之间，所有元素的和最大。例如：-2, 11, -4, 13, -5, -2时答案为20（11 -4 13）解法一穷举法：以前我想出了一种算法，具体做法是：取出所给序列的所有子序列求和,共分n组，第一组长度为1，有n个； 第二组长度为2, 有n-1个；，最后一组，长度为n,只有一个。比较这n(n1)/2个序列的和，再将每组的最大值比较，从而得到最大值以及其上下标。a1a2 an-1 ana1+a2 a2+a3 an-1+an a1+a2+a3 a2+a3+a4 . . .a1+a2.+an-1 a2+a3.+an a1+a2.+an-1+an此算法比较直接，也容易写出代码，但其时间开销为O(n2)，空间开销为O(n)，效率不高。解法二：动态规划求解，1、 样例求解过程：123456Ai-211-413-5-2Fi01172015132、 动态规划方程为：Fi：表示以元素i结尾的连续最大子序列的和那么对于第i个元素来说，要形成连续的最大子序列，只和相邻的前一个元素有关。因为可以不取，所以如果元素ai连接到以元素i-1结尾的最大连续子序列fi-1后是负数（fi-1+ai0 then fi:=fI-1+ai else fi:=0; max:=-maxlongint; for i:=1 to n do if fimax then max:=fi; 程序代码二：迭代进行 best:=-maxlongint;temp:=0;fori:=1tondobegintemp:=temp+ai);iftempbestthenbest:=temp;iftempai then fi:=fI-1+ai else fi:=ai; max:=-maxlongint; for i:=1 to n do if fimax then max:=fi; 第三种情况：至少要取两个。1、解法一：动态规划求解，2、样例求解过程：123456Ai-349-2-58Fi-3只能取一个-3+4=1取两个13=max4+9,9+111=Max9-2,13-26=max-2-5,11-514=Max-5+8,6+8 说明：以第4个元素为例： 选择一：取长度为2：9-2=7； 选择二：把元素a4连接到元素a3结尾的后面。F3+a4=13-2 两者最较大者。3、动态规划方程为：Fi：表示以元素i结尾的至少要取两个的连续最大子序列的和那么对于第i个元素来说，有两种选择：选择一：因至少要选两个，所以和为ai-1+ai;选择二：把ai连接到ai-1元素结尾的长度至少为2的最大连续子序列后。此时和为fi-1+ai;两种情况选较大者。所以动态方程：fi:=maxai-1+ai,fI-1+ai(i=3) (边界条件：f1=a1;f2=a1+a2)5、 代码： F1:=a1; f2:=a1+a2;for I:=3 to n do if (fI-1+ai)ai-1+ai then fi:=fI-1+ai else fi:=ai-1+ai; max:=-maxlongint; for i:=2 to n do if fimax then max:=fi; 其它情况：如2014年衢州市竞赛的转型，把相应的内容扩展到矩阵中而已。5、求M子段和的最值。问题描述：在一个长度为n的数列An中，求m个连续子序列，使得这m个连续子序列的和最大，且m个子序列无公共元素。特别地，若一子段的数全为负，则这个子段的和为0。（若两子段xi.j与yi.j不相交，则他们的关系是I=jI=j或I=jI=j）输入:第一行：n, m(1=n=100 1=m=10,m=n) n表示数列中有多少数 。第二行：n个数 每个数的绝对值=1000Sample Input5 2-5 9 -5 11 20Sample Output401、分析：在连续最大子序列和的基础上“加一维”的思想，同样利用动态规划来解决。用ansi,j表示数列前j个元素中，i个无公共元素的子序列的最大和，且必须包含第j个元素，a存放数列元素.2、则状态转移方程为： 对于第j 个元素，可以单独成一个段，也可以和前面的相连。 选择一：如果元素aj单独成一段，那么前面长度为k的序列，划分成不相交的 i-1段，能得的和为ansi-1,k+aj; 选择二：如果元素aj连接在第i段，那么前面j-1个元素分成不相交的i段，aj作为第i段的最后一个元素连上即可。能得到的和为ansI,j-1+aj 两者取较大值。ansi,j=maxansi,j-1+aj,ansi-1,k+a(i-1=kansi,jthenansi,j:=ansi-1,k+noj;end;fori:=1tondoifansm,ibestthenbest:=ansm,i;注意：红色部分为确定最大值的过程！因为ansi,j表示数列前j个元素中，i个无公共元素的子序列的最大和，且最大和不一