2025年最大子数组问题

科技前沿 • 2025-02-17 08:36 • 阅读 70

大家好，我是讯享网，很高兴认识大家。

最大子数组问题

定义

Max Continuous Subarray ,MCS

输入

给定一个数组X[1…n],对于任意一对数组下标为l,r(l<=r)的非空子数组,其和记为S(l,r)

输出

求出S(l,r)的最大值,记为Smax

解决方案一: 蛮力枚举

输入数组X[1…n]

伪代码:

int Smax=0; for (l=1;l<=n;l++) { for(int r=l;l<=n;r++) { S(l,r)=0; for(i=l;i<=r;i++) { S(l,r)+=X[i]; } Smax=max{Smax,S(l,r)}; } } return Smax;

讯享网

时间复杂度: O(n^3)

解决方案二: 优化枚举法

讯享网Smax=0; for(l=1;l,=n;l++) { S=0; for(r=l;r<=n;r++) { S+=X[r]; Smax=max{Smax,S}; } } return Smax;

时间复杂度 : O(n^2)

解决方案三: 分为治之

将数组X[1…n]分为X[1…n/2] 和 X[n/2+1…n]

递归求解子问题

S1: 数组X[1…n/2]的最大子数组

S2: 数组X[n/2+1…n]的最大子数组

合并子问题,得到Smax

S3: 跨中点的最大子数组

数组X的最大子数组之和Smax=max{S1,S2,S3}

讯享网

输入:数组X,数组下标low,high

输出: 最大子数组之和Smax

if(low==high) return X[low]; else { int mid = (low+high)/2; S1=MaxSubArray(X,low,mid); S2=MaxSubArray(mid+1,high); S3=CrossingSubArray(X,low,mid,high); Smax=max{S1,S2,S3}; return Smax; }

时间复杂度 : O(n logn)

解决方案四: 动态规划

Di: 以X[i]开头的最大子数组和

Si: 以X[i]开头的任一子数和

初始化:

D[n]=X[n]

递推公式:

D[i+1]>0 D[i]=X[i]+D[i+1]

D[i=1]<0 D[i]=X[i]

构造追踪数组Rec[1…n]

结尾相同:Rec[i]=i

在这里插入图片描述

输入:数组X,数组长度n

输出: 最大子数组和Smax,子数组起始位置l,r

新建一维数组D[1…n] ,Rec[1…n]

讯享网//初始化 int D[n],Rec[n] D[n] =X[n]; Rec[n]=n; //动态规划 for (i=n-1;i<=1;i--) { if(D[i+1]>0) { D[i]=X[i]+D[i+1]; Rec[i]=Rec[i+1]; } else { D[i]=X[i]; Rec[i]=i; } } //查找解 Smax =D[1]; for (i=2;i<=n;i++) { if(Smax<D[i]) { Smax=D(i); l=i; r=Rec[i]; } } return Smax,l,r;

时间复杂度: O(n)