从连续最大和到最优子矩阵

《从连续最大和到最优子矩阵》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、从连续最大和到最优子矩阵。2009-02-0716:34声明：此为转载，此篇也在noi专刊上刊登过。从连续最大和到最优子矩阵郑州市第101中学2009届学生：史沛关键字：连续最大和最优子矩阵动态规划矩阵数据压缩从这次省选落选后，我发现有两个东西是自己极为欠缺的：1、动态规划；2、矩阵的相关知识；所以，这次好好地学习了一下矩阵和动态规划相结合的一些知识。为了以后能够铭记在心，特写一篇论文，一来，帮助那些还不清楚的OIers；二来，供自己日后参看。——题记一、数列的连续最大和在谈及最优子矩阵之前，我们先来做一些准备工作，即：数列的连续最大和，顾名思义，就是在一个长度为n的数列{An}

2、中，求i，j（1<=i<=j<=n），使得数列{An}中，第i个元素到第j个元素之间，所有元素的和最大。由于是连续，初学者往往想到的是枚举，然而枚举的时间复杂度是难以接受的。顾思考更高效的算法——动态规划。仔细思考题目后，符合动态规划条件。用ans[i]表示包含数列第i项的前i个元素的最大和，数组no存放数列元素，则状态转移方程为：ans[0]=0；ans[i]=max{ans[i-1]+no[i],no[i]}时间复杂度为O(n)核心程序代码：best:=-maxlongint;temp:=0;fori:=1tondobegininc(temp,no[i]);iftemp>be

3、stthenbest:=temp;iftemp<0thentemp:=0;end;注意：红色循环体部分的顺序万万不可颠倒！[问题拓展]：在一个长度为n的数列{An}中，求m个连续子序列，使得这m个连续子序列的和最大，且m个子序列无公共元素。解决类似的问题，我们可以利用“加一维”的思想利用动态规划来解决。用ans[i,j]表示数列前j个元素中，i个无公共元素的子序列的最大和，且必须包含第j个元素，数组no存放数列元素，则状态转移方程为：ans[i,j]=max{ans[i,j-1]+no[j],ans[i-1,k]+no[j]}(i-1<=k<=j-1)时间复杂度为O(n^3)何训

4、程序代码：fori:=1tomdoforj:=itondobeginans[i,j]:=ans[i,j-1]+no[j];fork:=i-1toj-1doifans[i-1,k]+no[j]>ans[i,j]thenans[i,j]:=ans[i-1,k]+no[j];end;fori:=1tondoifans[m,i]>bestthenbest:=ans[m,i];注意：红色部分为确定最大值的过程！因为ans[i,j]表示数列前j个元素中，i个无公共元素的子序列的最大和，且最大和不一定非要取完所有的元素，所以用一个循环来检测所有m的连续子序列的元素最大和，以确定全局最优值！二、

5、最优子矩阵有了前面的铺垫，我们就可以导论最优子矩阵的问题了，换句话说，最优子矩阵是建立在数列连续最大和的基础上的。所谓最优子矩阵，就是指在一个n*m二维的矩阵中，确定一个小的矩阵，使这个小矩阵中所有元素的和最大。思考一下最优子矩阵和连续最大和的异同：1、所求的和都具有连续性；2、连续最大和是一维问题，最优子矩阵是二维问题另外，对于一个矩阵而言，如果我们将连续k行的元素纵向相加，并对相加后所得的数列求连续最大和，则此连续最大和就是一个行数为k的最优子矩阵！由此，我们可以将二维的矩阵压缩成一维矩阵，转换为线性问题，从而求解。故问题的关键在于如何用高效的压缩方式存储、读取矩阵。下面具一

6、个简单的例子。在一个一维的数列中，要想求从第i个元素到第j个元素的和，我们可以用这样的方法：设数组sum[i]表示从第1个到第i个元素的和，则：求从第i个元素到第j个元素的和，只需用sum[j]-sum[i]就足够了。由此推广到二维矩阵，设sum[i,j]表示矩阵第j列前i个元素的和，cost[i,j]表示原始数据，则：压缩数据程序代码为：fori:=1tondoforj:=1tomdosum[i,j]:=sum[i-1,j]+cost[i,j];下一个问题是，如何将数据从压缩的数组中读出。下面，我们来分析、推导一下：假设n=3的情况，不同的组合情况和数据处理方法如下表：(1<=

7、j<=m)不同的行组合数据处理方法第一行sum[1,j]第二行sum[2,j]-sum[1,j]第三行sum[3,j]-sum[2,j]第一、二行sum[2,j]第二、三行sum[3,j]-sum[1,j]第一、二、三行sum[3,j]我们将数据处理方法简写、并加以整理可得：3-2，3-1，3-02-1，2-0，1-0不失一般性，可设两个循环变量，外层(i)从n到1，内层(j)从i-1到0。设数组temp用来存储临时的数列，则：读取数据代码为：fori:=ndownto1dofo