OI基础系列之最大子数组问题-白红宇

OI基础系列之最大子数组问题

阅读量：6251 次

发布时间：2019-06-22

本文共 9900 字，大约阅读时间需要 33 分钟。

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 sum>max then max:=sum;

end;

writeln(max);

end.

C++版：

#include<iostream>

using namespace std;

int main()

{

long n,a[1001];

cin>>n;

for(long i=0;i!=n;i++)cin>>a[i];

long max=-0x3fffffff,sum;

for(long i=0;i!=n;i++)

for(long j=i;j!=n;j++)

{

sum=0;a

for(long k=i;k<=j;k++)

sum+=a[k];

if(sum>max)max=sum;

}

cout<<max<<endl;

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++版：

#include<iostream>

using namespace std;

int main()

{

long n,a[1001];

cin>>n;

a[0]=0;

for(long i=1;i<=n;i++)

{

cin>>a[i];

a[i]+=a[i-1];

}

long max=-0x3fffffff;

for(long i=1;i<=n;i++)

for(long j=i;j<=n;j++)

if(a[j]-a[i-1]>max)

max=a[j]-a[i-1];

cout<<max<<endl;

return 0;

}

三、分治法时间复杂度：O(nlgn) 空间复杂度：O(n)

这个方法是从《算法导论》上看到的方法，虽然算法不是最优的，但是整个算法的思路还是很有启发性的。这里引用《算法导论》的原话（略有删改）：

我们来思考如何用分治法技术来求解最大子数组问题。假定我们要寻求子数组A[low..high]的最大子数组。使用分治技术以为这我们要将子数组划分为两个规模尽量相等的子数组。也就是说，寻找子数组的中央位置，比如mid，然后考虑求解两个子数组A[low..mid]和A[mid+1..high]。A[low..high]的任何连续子数组A[i..j]所处的位置必然是一下三种情况之一：

完全位于子数组A[low..mid]中，因此low<=i<=j<=mid。

完全位于子数组A[mid+1..high]中，因此mid<i<=j<=high。

跨越了中点，因此low<=i<=mid<j<=high。

因此，A[low..high]的一个最大子数组所处的位置必然是这三种情况之一。实际上，A[low..high]的一个最大子数组必然是完全位于A[low..mid]中、完全位于A[mid+1..high]中或者跨越中点的所有子书中和最大者。我们可以递归地求解A[low..mid]和A[mid+1..high]的最大子数组，因此这两个子问题仍是最大子数组问题，只是规模更小。因此，剩下的全部工作就是寻找跨越中点的最大子数组，然后在三种情况下选取和最大者。

我们可以很容易地在线性时间（相对于子数组A[low..high]的规模）内求出跨越中点的最大子数组。此问题并非原问题规模更小的实例，因此它加入了限制——求出的子数组必须跨越中点。任何跨越中点的子数组都有两个子数组A[i..mid]和A[mid+1..j]组成，其中low<=i<=mid且mid<j<=high。因此，我们只需找出形如A[i..mid]和A[mid+1..j]的最大子数组，然后将其合并即可。

而因为A[i..mid]和A[mid+1..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 a>b 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:=mid+1 to high do

begin

inc(sum,a[i]);

right_sum:=max(right_sum,sum);

end;

exit(left_sum+right_sum);

end;

function find_maximum_subarray(low,high):longint;

var

mid,maxn:longint;

begin

if high=low then exit(a[low]);

mid:=(low+high) div 2; //类似的，这样写 mid:=(low+high)>>1; 也行。

maxn:=find_max_crossing_subarray(low,mid,high);

maxn:=max(maxn,find_maximum_subarray(low,mid));

maxn:=max(maxn,find_maximum_subarray(mid+1,high));

exit(maxn);

end;

begin

readln(n);

for i:=1 to n do read(a[i]);

writeln(find_maximum_subarray(1,n));

end.

C++版：

#include<iostream>

#define min_num -0x3fffffff

using namespace std;

long a[100001];

long max(long a,long b){return (a>b)?a:b;}

long find_max_crossing_subarray(long low,long mid,long high)

{

long left_sum=min_num,sum=0;

for(long i=mid;i>=low;i--)

{

sum+=a[i];

left_sum=max(left_sum,sum);

}

long right_sum=min_num; sum=0;

for(long i=mid+1;i<=high;i++)

{

sum+=a[i];

right_sum=max(right_sum,sum);

}

return left_sum+right_sum;

}

long find_maximum_subarray(long low,long high)

{

if(low==high)return a[low];

long mid=(low+high)/2;

long maxn=find_max_crossing_subarray(low,mid,high);

maxn=max(maxn,find_maximum_subarray(low,mid));

maxn=max(maxn,find_maximum_subarray(mid+1,high));

return maxn;

}

int main()

{

long n; cin>>n;

for(long i=1;i<=n;i++)cin>>a[i];

cout<<find_maximum_subarray(1,n)<<endl;

return 0;

}

四、动态规划法（DP）时间复杂度：O(n) 空间复杂度：O(n)

设f[i]表示a[1..i]的最大子数组。设想我们已经求出f[i]，如何扩展到f[i+1]？仔细思考后会发现，在已知f[i]的前提下，f[i+1]不外乎就两种情况：一种是f[i+1]不包含a[i+1]，那么显然f[i+1]=f[i]。另一种是f[i+1]包含a[i+1]，那么f[i+1]显然是a[j..i+1]（1<=j<=i+1）中最大的那个，不妨设max{a[j..i+1]}(1<=j<=i+1)为g[i+1]，那么显然g[i+1]就是表示以a[i+1]结尾的最大子数组。

假设我们已经求出了g[i+1]，那么依据上面所述，便可得f[i+1]的状态转移方程：

f[i+1]=max{f[i],g[i+1]}

现在问题已经成功转化为求g[i+1]。还是按照同样的思路去想，假设我们已经求出g[i]，如何扩展到g[i+1]？同样也就两种情况：一种是g[i]为负数，那么显然g[i+1]=a[i+1]；另外一种g[i]不是负数，那么g[i+1]=g[i]+a[i+1]。所以，g[i+1]的为状态转移方程：

g[i+1]=max{g[i]+a[i+1],a[i+1]}

综上所述我们便得到了整个问题的状态转移方程：

f[i+1]=max{f[i],g[i+1]}

g[i+1]=max{g[i]+a[i+1],a[i+1]}

多说一句，如果你对这种含有多个数组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 a>b 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++版：

#include<iostream>

#define maxn 100001

#define min_num -0x3fffffff

using namespace std;

long max(long a,long b){return (a>b)?a:b;}

int main()

{

long n,a[maxn],f[maxn],g[maxn]; cin>>n;

for(long i=1;i<=n;i++)cin>>a[i];

f[0]=min_num; g[0]=min_num;

for(long i=1;i<=n;i++)

{

g[i]=max(g[i-1],0)+a[i];

f[i]=max(f[i-1],g[i]);

}

cout<<f[n]<<endl;

return 0;

}

五、动态规划法（空间优化版）时间复杂度O(n) 空间复杂度O(1)

好吧，我承认这种方法就是闲的蛋疼，没太大实质性优化，拿出来给大家参考一下。

回顾下上面方法的状态转移方程：

f[i+1]=max{f[i],g[i+1]}

g[i+1]=max{g[i]+a[i+1],a[i+1]}

你会发现无论是f[i]还是g[i]都只与前一项有关，想到了什么，滚动数组！（不知道的自行百度，很多大神的文章讲的都很详细）自然而然就有了这种方法(用了位运算的知识，不会的同样百度，推荐Matrix67神牛讲解位运算的文章)。表达式如下：

PASCAL:

f[(i+1) and 1]=max{f[i and 1],g[(i+1) and 1]}

g[(i+1) and 1]=max(g[i and 1]+a[(i+1) and 1],a[(i+1) and 1]

C++:

f[(i+1)&1]=max{f[i&1],g[(i+1)&1]}

g[(i+1)&1]=max(g[i&1]+a[(i+1)&1],a[(i+1)&1]

PASCAL版：

program ed;

var

i,n,a:longint;

f,g:array[0..1] of longint;

function max(a,b:longint):longint;

begin

if a>b 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++版：

#include<iostream>

#include<cstdlib>

#define min_num -0x3fffffff

using namespace std;

int main()

{

long n,a,f[2]={min_num,min_num},g[2]={min_num,min_num}; cin>>n;

for(long i=1;i<=n;i++)

{

cin>>a;

g[i&1]=max(g[(i-1)&1]+a,a);

f[i&1]=max(f[(i-1)&1],g[i&1]);

}

cout<<f[n&1]<<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 a>b 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++版：

#include<iostream>

#include<cstdlib>

#define min_num -0x3fffffff

using namespace std;

int main()

{

long n,a,ans=min_num,g[2]={min_num,min_num}; cin>>n;

for(long i=1;i<=n;i++)

{

cin>>a;

g[i&1]=max(g[(i-1)&1]+a,a);

ans=max(ans,g[i&1]);

}

cout<<ans<<endl;

return 0;

}

七、一种新的思路——转化问题时间复杂度O(n) 空间复杂度O(n)

放在这里并不是说这种方法比上面的要好，只是思路比较新颖。

设b[i]表示a[1..i]的和，那么问题转化为求i,j(i<=j)，使b[j]-b[i]的差最大。记f[i]表示b[i..n]的最大值。那么答案显然是f[i]-b[i]的最大值。

f[i]可以在线性时间内求出来，状态转移方程如下：

f[i]=max{f[i+1],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 a>b 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[n+1]:=-maxlongint;

for i:=n downto 0 do

begin

f[i]:=max(f[i+1],a[i]);

ans:=max(ans,f[i]-a[i]);

end;

writeln(ans);

end.

C++版：

#include<iostream>

#include<cstdlib>

#define min_num -0x3fffffff

using namespace std;

int main()

{

long n,a[

long ans=min_num; f[n+1]=min_num;

for(long i=n;i>=0;i--)

{

f[i]=max(f[i+1],a[i]);

ans=max(ans,f[i]-a[i]);

}

cout<<ans<<endl;

return 0;

}

八、最大子数组问题的扩展——最大子矩阵时间复杂度：O(n^3) 空间复杂度：O(n^2)

现在我们将最大子数组问题扩展到2维，变成最大子矩阵问题。即在一个二维数组中找一个最大子矩阵。这里用到的方法就是把最大子矩阵问题转化为最大子数组问题解决。说的具体点就是枚举矩阵行的上下界，设二维数组为a[m][n],假设枚举上下界为i,j(i<=j)，那么b[k]=a[t][k](i<=t<=j)的和。这样就可以用最大子数组的方法。枚举的时间复杂度为O(n^2)，和可以用与算法二类似的方法预处理，最后最大子数组时间复杂度为O(n)，所以最大子矩阵问题的时间复杂度：O(n^3)。

经典的问题如AHOI2011的第一题，以及RQNOJ上的某题。当然这个问题还能扩展到三维、四维乃至更高维，基本上对于M维的问题，用类似的方法可以写出一个时间复杂度O(n^(2M-1))，空间复杂度O（n^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 a>b then exit(a); exit(b);

end;