网站开发 聊天窗口,济南 网站建设那家好,网站建设实训心得,泰安城建吧OI基础系列之最大子数组问题 ——Edward2414 oi退役了#xff0c;虽然没取得多少成绩#xff0c;也算是走过一会的人了。我相信绝大多数oi党都是自学成才#xff0c;在此#xff0c;我感谢那些把自己所学写到博客里的前辈们#xff0c;没有你们#xff0c;我不可能… OI基础系列之最大子数组问题 ——Edward2414 oi退役了虽然没取得多少成绩也算是走过一会的人了。我相信绝大多数oi党都是自学成才在此我感谢那些把自己所学写到博客里的前辈们没有你们我不可能学到那么多的知识。所以从今天起我也会将自己的一些所学所得写下来给后面的人做个参考,讲的都是很基础的东西大神请直接无视。笔者水平有限有疏漏之处还望指出。 今天说的叫最大子数组问题大意是一个长度为n的数组中求一个子数组使这个子数组是所有子数组中元素和最大的那个。 一、最最朴素的算法 时间复杂度O(n^3) 空间复杂度O(n) 直接枚举每个字数组的首尾并求和后与max比较即可。 PASCAL版 //没安PASCAL编译器所以细节上可能有些问题大家凑合看。 program ed; var i,j,k,n,max,sum:longint; a:array[0..1001] of longint; begin readln(n); for i:1 to n do read(a[i]); max:-maxlongint; for i:1 to n do for j:i to n do begin sum:0; for k:i to j do inc(sum,a[k]); if summax then max:sum; end; writeln(max); end. C版 #includeiostream using namespace std; int main() { long n,a[1001]; cinn; for(long i0;i!n;i)cina[i]; long max-0x3fffffff,sum; for(long i0;i!n;i) for(long ji;j!n;j) { sum0;a for(long ki;kj;k) suma[k]; if(summax)maxsum; } coutmaxendl; return 0; } 二、朴素的算法 时间复杂度O(n^2) 空间复杂度O(n) 在算法一的基础上考虑到每个子数组的和是可以预先求出来的。即预先求出sum[i]表示a[1] 到a[i]所有数的和这样a[i]到a[j]的和就可以表示为sum[j]-sum[i-1]这样就可以省去第三重循环把算法的时间复杂度降到O(n^2)。 PASCAL版 program ed; var i,j,n,max:longint; a,sum:array[0..1001] of longint; begin readln(n); for i:1 to n do read(a[i]); sum[0]0; for i:1 to n do sum[i]:sum[i-1]a[i]; max:-maxlongint; for i:1 to n do for j:i to n do If sum[j]-sum[i-1]max then max:sum[j]-sum[i-1]; writeln(max); end. C版 #includeiostream using namespace std; int main() { long n,a[1001]; cinn; a[0]0; for(long i1;in;i) { cina[i]; a[i]a[i-1]; } long max-0x3fffffff; for(long i1;in;i) for(long ji;jn;j) if(a[j]-a[i-1]max) maxa[j]-a[i-1]; coutmaxendl; return 0; } 三、分治法 时间复杂度O(nlgn) 空间复杂度O(n) 这个方法是从《算法导论》上看到的方法虽然算法不是最优的但是整个算法的思路还是很有启发性的。这里引用《算法导论》的原话略有删改 我们来思考如何用分治法技术来求解最大子数组问题。假定我们要寻求子数组A[low..high]的最大子数组。使用分治技术以为这我们要将子数组划分为两个规模尽量相等的子数组。也就是说寻找子数组的中央位置比如mid然后考虑求解两个子数组A[low..mid]和A[mid1..high]。A[low..high]的任何连续子数组A[i..j]所处的位置必然是一下三种情况之一 完全位于子数组A[low..mid]中因此lowijmid。完全位于子数组A[mid1..high]中因此midijhigh。跨越了中点因此lowimidjhigh。 因此A[low..high]的一个最大子数组所处的位置必然是这三种情况之一。实际上A[low..high]的一个最大子数组必然是完全位于A[low..mid]中、完全位于A[mid1..high]中或者跨越中点的所有子书中和最大者。我们可以递归地求解A[low..mid]和A[mid1..high]的最大子数组因此这两个子问题仍是最大子数组问题只是规模更小。因此剩下的全部工作就是寻找跨越中点的最大子数组然后在三种情况下选取和最大者。 我们可以很容易地在线性时间相对于子数组A[low..high]的规模内求出跨越中点的最大子数组。此问题并非原问题规模更小的实例因此它加入了限制——求出的子数组必须跨越中点。任何跨越中点的子数组都有两个子数组A[i..mid]和A[mid1..j]组成其中lowimid且midjhigh。因此我们只需找出形如A[i..mid]和A[mid1..j]的最大子数组然后将其合并即可。 而因为A[i..mid]和A[mid1..j]相互独立我们可以很容易的在O(n)时间内分开求出他们的最大子数组。 PASCAL版 //再次声明笔者没有PASCAL的编译器所有程序都是对着C手码的仅仅方便//pascaler的理解不保证正确。 program ed; var a:array[0..100001] of longint; i,n:longint; function max(a,b:longint):longint; begin if ab then exit(a); exit(b); end; function find_max_crossing_subarray(low,mid,high):longint; var left_sum,right_sum,sum,i:longint; begin left_sum:-maxlongint; sum:0; for i:mid downto low do begin inc(sum,a[i]); left_sum:max(left_sum,sum); end; right_sum:-maxlongint; sum:0; for i:mid1 to high do begin inc(sum,a[i]); right_sum:max(right_sum,sum); end; exit(left_sumright_sum); end; function find_maximum_subarray(low,high):longint; var mid,maxn:longint; begin if highlow then exit(a[low]); mid:(lowhigh) div 2; //类似的这样写 mid:(lowhigh)1; 也行。 maxn:find_max_crossing_subarray(low,mid,high); maxn:max(maxn,find_maximum_subarray(low,mid)); maxn:max(maxn,find_maximum_subarray(mid1,high)); exit(maxn); end; begin readln(n); for i:1 to n do read(a[i]); writeln(find_maximum_subarray(1,n)); end. C版 #includeiostream #define min_num -0x3fffffff using namespace std; long a[100001]; long max(long a,long b){return (ab)?a:b;} long find_max_crossing_subarray(long low,long mid,long high) { long left_summin_num,sum0; for(long imid;ilow;i--) { suma[i]; left_summax(left_sum,sum); } long right_summin_num; sum0; for(long imid1;ihigh;i) { suma[i]; right_summax(right_sum,sum); } return left_sumright_sum; } long find_maximum_subarray(long low,long high) { if(lowhigh)return a[low]; long mid(lowhigh)/2; long maxnfind_max_crossing_subarray(low,mid,high); maxnmax(maxn,find_maximum_subarray(low,mid)); maxnmax(maxn,find_maximum_subarray(mid1,high)); return maxn; } int main() { long n; cinn; for(long i1;in;i)cina[i]; coutfind_maximum_subarray(1,n)endl; return 0; } 四、动态规划法DP 时间复杂度O(n) 空间复杂度O(n) 设f[i]表示a[1..i]的最大子数组。设想我们已经求出f[i]如何扩展到f[i1]仔细思考后会发现在已知f[i]的前提下f[i1]不外乎就两种情况一种是f[i1]不包含a[i1]那么显然f[i1]f[i]。另一种是f[i1]包含a[i1]那么f[i1]显然是a[j..i1]1ji1中最大的那个不妨设max{a[j..i1]}(1ji1)为g[i1]那么显然g[i1]就是表示以a[i1]结尾的最大子数组。 假设我们已经求出了g[i1]那么依据上面所述便可得f[i1]的状态转移方程 f[i1]max{f[i],g[i1]} 现在问题已经成功转化为求g[i1]。还是按照同样的思路去想假设我们已经求出g[i]如何扩展到g[i1]同样也就两种情况一种是g[i]为负数那么显然g[i1]a[i1]另外一种g[i]不是负数那么g[i1]g[i]a[i1]。所以g[i1]的为状态转移方程 g[i1]max{g[i]a[i1],a[i1]} 综上所述我们便得到了整个问题的状态转移方程 f[i1]max{f[i],g[i1]} g[i1]max{g[i]a[i1],a[i1]} 多说一句如果你对这种含有多个数组DP很感兴趣推荐做一下RQNOJ上的又上锁妖塔一题也是这个类型的。还有一道USACO的一道奶牛跑步的题目用的也是这个方法具体哪一题记不清了有兴趣可以去找一下。 PASCAL版 program ed; var a,f,g:array[0..100001] of longint; i,n:longint; fucntion max(a,b:longint):longint; begin if ab then exit(a); exit(b); end; begin readln(n); for i:1 to n do read(a[i]); f[0]:-maxlongint; g[0]:-maxlongint; for i:1 to n do begin g[i]:max(g[i-1],0)a[i]; f[i]:max(f[i-1],g[i]); end; writeln(f[n]); end. C版 #includeiostream #define maxn 100001 #define min_num -0x3fffffff using namespace std; long max(long a,long b){return (ab)?a:b;} int main() { long n,a[maxn],f[maxn],g[maxn]; cinn; for(long i1;in;i)cina[i]; f[0]min_num; g[0]min_num; for(long i1;in;i) { g[i]max(g[i-1],0)a[i]; f[i]max(f[i-1],g[i]); } coutf[n]endl; return 0; } 五、动态规划法空间优化版 时间复杂度O(n) 空间复杂度O(1) 好吧我承认这种方法就是闲的蛋疼没太大实质性优化拿出来给大家参考一下。 回顾下上面方法的状态转移方程 f[i1]max{f[i],g[i1]} g[i1]max{g[i]a[i1],a[i1]} 你会发现无论是f[i]还是g[i]都只与前一项有关想到了什么滚动数组不知道的自行百度很多大神的文章讲的都很详细自然而然就有了这种方法(用了位运算的知识不会的同样百度推荐Matrix67神牛讲解位运算的文章)。表达式如下 PASCAL: f[(i1) and 1]max{f[i and 1],g[(i1) and 1]} g[(i1) and 1]max(g[i and 1]a[(i1) and 1],a[(i1) and 1] C: f[(i1)1]max{f[i1],g[(i1)1]} g[(i1)1]max(g[i1]a[(i1)1],a[(i1)1] PASCAL版 program ed; var i,n,a:longint; f,g:array[0..1] of longint; function max(a,b:longint):longint; begin if ab then exit(a); exit(b); end; begin readln(n); f[0]:-maxlongint; f[1]:-maxlongint; g[0]:-maxlongint; g[1]:-maxlongint; for i:1 to n do begin read(a); g[i and 1]:max(g[(i-1) and 1],0)a; f[i and 1]:max(f[(i-1) and 1],g[i and 1]; end; writeln(f[n and 1]); end. C版 #includeiostream #includecstdlib #define min_num -0x3fffffff using namespace std; int main() { long n,a,f[2]{min_num,min_num},g[2]{min_num,min_num}; cinn; for(long i1;in;i) { cina; g[i1]max(g[(i-1)1]a,a); f[i1]max(f[(i-1)1],g[i1]); } coutf[n1]endl; return 0; } 六、动态规划法2 时间复杂度O(n) 空间复杂度O(1) 换一个思路想想其实f[i]数组是不必要的。因为最大子数组一定是以某一个a[i]结尾的所以答案就是g[i]的最大值。 PASCAL版 program ed; var i,n,a,ans:longint; g:array[0..1] of longint; function max(a,b:longint):longint; begin if ab then exit(a); exit(b); end; begin readln(n); g[0]:-maxlongint; g[1]:-maxlongint; ans:-maxlongint; for i:1 to n do begin read(a); g[i and 1]:max(g[(i-1) and 1],0)a; ans:max(ans,g[i and 1]); end; writeln(ans); end. C版 #includeiostream #includecstdlib #define min_num -0x3fffffff using namespace std; int main() { long n,a,ansmin_num,g[2]{min_num,min_num}; cinn; for(long i1;in;i) { cina; g[i1]max(g[(i-1)1]a,a); ansmax(ans,g[i1]); } coutansendl; return 0; } 七、一种新的思路——转化问题 时间复杂度O(n) 空间复杂度O(n) 放在这里并不是说这种方法比上面的要好只是思路比较新颖。 设b[i]表示a[1..i]的和那么问题转化为求i,j(ij)使b[j]-b[i]的差最大。记f[i]表示b[i..n]的最大值。那么答案显然是f[i]-b[i]的最大值。 f[i]可以在线性时间内求出来状态转移方程如下 f[i]max{f[i1],b[i]} 有了f[i],答案就显而易见了。 PASCAL版 program ed; var a,f:array[0..100001] of longint; i,n,ans:longint; function max(a,b:longint):longint; begin if ab then exit(a); exit(b); end; begin readln(n); for i:1 to n do begin read(a[i]); inc(a[i],a[i-1]); end; ans:-maxlongint; f[n1]:-maxlongint; for i:n downto 0 do begin f[i]:max(f[i1],a[i]); ans:max(ans,f[i]-a[i]); end; writeln(ans); end. C版 #includeiostream #includecstdlib #define min_num -0x3fffffff using namespace std; int main() { long n,a[ long ansmin_num; f[n1]min_num; for(long in;i0;i--) { f[i]max(f[i1],a[i]); ansmax(ans,f[i]-a[i]); } coutansendl; return 0; } 八、最大子数组问题的扩展——最大子矩阵 时间复杂度O(n^3) 空间复杂度O(n^2) 现在我们将最大子数组问题扩展到2维变成最大子矩阵问题。即在一个二维数组中找一个最大子矩阵。这里用到的方法就是把最大子矩阵问题转化为最大子数组问题解决。说的具体点就是枚举矩阵行的上下界设二维数组为a[m][n],假设枚举上下界为i,j(ij)那么b[k]a[t][k](itj)的和。这样就可以用最大子数组的方法。枚举的时间复杂度为O(n^2)和可以用与算法二类似的方法预处理最后最大子数组时间复杂度为O(n)所以最大子矩阵问题的时间复杂度O(n^3)。 经典的问题如AHOI2011的第一题以及RQNOJ上的某题。当然这个问题还能扩展到三维、四维乃至更高维基本上对于M维的问题用类似的方法可以写出一个时间复杂度O(n^(2M-1))空间复杂度On^M的算法。比较经典的例子就是RQNOJ上的切西瓜这题。 下面给出二维情况的代码 PASCAL版 program ed; var a:array[0..101,0..101] of longint; f:array[0..101] of longint; i,j,k,m,n,ans:longint; function max(a,b:longint):longint; begin if ab then exit(a); exit(b); end; begin readln(m,n); for i:1 to m do begin for j:1 to n do begin read(a[i,j]); inc(a[i,j],a[i-1,j]); end; readln; end; ans:-maxlongint; for i:1 to m do for j:i to m do begin f[0]:-maxlongint; for k:1 to n do begin f[k]:max(f[k-1],0)a[j,k]-a[i-1,k]; ans:max(ans,f[k]); end; end; writeln(ans); end. C版 #includeiostream #includecstdlib #define min_num -0x3fffffff using namespace std; int main() { long m,n,a[101][101],f[101]; cinmn; for(long i1;in;i)a[0][i]0; for(long i1;im;i) for(long j1;jn;j) { cina[i][j]; a[i][j]a[i-1][j]; } long ansmin_num; for(long i1;im;i) for(long ji;jm;j) { f[0]min_num; for(long k1;kn;k) { f[k]max(f[k-1]a[j][k]-a[i-1][k],a[j][k]-a[i-1][k]); ansmax(ans,f[k]); } } coutansendl; return 0; } 至此最大子数组问题就就告一段落了。作者本人水平有限如果读者发现内容中的错误或是有什么建议希望予以指出。 本文由Edward2414创作转载请注明出处。转载于:https://www.cnblogs.com/edward2414/archive/2013/03/27/oi-01.html
