1维的最大子数组之和
对于1维的最大子数组之和
假设f[i]表示:对于1..i这个序列中,包含i这个元素的最大序列的值
则对于f[i],0<i<=n;
应该有
f[i]=max(a[i],f[i-1]+a[i]);
f[1]=a[1];
由此一维的问题即可解决
时间复杂度:O(n);
空间复杂度:O(n);
2维的最大子数组之和
为了叙述的方便,在此我们先约定,输入的矩阵为P,行和列值分别约定为m,n
对于2维数组,我们虽然无法直接使用1维中的动态规划的思路
但是,如果我们可以把一整行看做一个元素
按照1维的思路,我们就可以得到一个最大的m*x的矩阵A,0<x<n
显然A不一定是最后的答案,因为矩阵A的行值被我们限定为了m
所以我们需要枚举m,即m←1..m
之后要做的就很简单了
枚举行值等于m,列值恒定为n的所有矩阵D,并找出D中的最大子矩阵E
对于所有的E,max(E)就是最后的答案
时间复杂度=T[求1维最大子数组]*T[枚举矩阵]*T[计算矩阵每一行的值]
前者已知为O(n)
枚举矩阵则需要一个二重的循环,即为O(n^2)
对于计算矩阵D中没一行的值
我们可以进行预处理
假设D在P中的位置为:第x列→第y列
如果我们用一个数组g[i][j]表示:第i行的1..j列的元素之和为g[i][j];
则对于D中的每一行的和应该为g[i][y]-g[i][x],(0<i<=m)
每次计算的复杂度为O(1)
所以总的时间复杂度为:O(N^3)
空间复杂度:
主要用于存储P,D,E
为:O(n^2);
曲面2维的最大子数组之和
曲面和平面最本质的区别就是:边缘的连续问题
所以我们只需要增加3个矩阵P1,P2,P3,排列为:
P P1
P2 P3
求解其中和最大的子矩阵E即可
但对于E,行列值均应分别小于m,n;
时间空间复杂度均和2维平面最大子数组之后的复杂度相同
时间复杂度:O(n^3);
空间复杂度:O(n^2);
以下是作业所需要包含的必要的东西
开发时间:30min
效率:不知道该如何描述
心得:第一次写Blog,把自己所想的准确的表达出来,也不是想象中那么简单
截图:这是一个在线OJ的评测截图,因为有个题目和这个一样,所以我就偷了个懒,没有自己写测试数据 : ]
下面是二维平面最大子数组的源码,由于比较简短,我也就没有做过多的注释
如果有不明白或者觉得本人写的代码不够简洁或者有误,也欢迎各位留言
#include<stdio.h>
#define M 100
#define max(a,b) (a)>(b)?(a):(b) /* 由于比较懒,在此我先预处理了P的所有子矩阵的,每一行的值 所以开销为O(n^3) 但此算法的空间复杂度是可以为o(n^2)的 但需要每次初始化一下数组的值 所以我就比较懒的开了个O(n^3)的复杂度 : ] */ int f[M][M][M],g[M][M][M],a[M][M],i,j,k,l,n,m; main()
{
//输入
scanf("%d%d",&m,&n);
for(i=;i<m;i++)
for(j=;j<n;j++)
scanf("%d",a[i]+j); //预处理矩阵每一行的值
for(i=;i<m;i++)
for(j=;j<n;j++)
for(k=j;k>=;k--)
g[i][j][k]=g[i][j][k+]+a[i][k]; //C中,防止指针值越界,而提前处理初值
for(i=;i<n;i++)
for(j=;j<=i;j++){
f[][j][i]=g[][j][i];
l=max(l,f[][i][j]);
} //求解过程
for(i=;i<m;i++)
for(j=;j<n;j++)
for(k=;k<=j;k++){
f[i][j][k]=max(g[i][j][k],f[i-][j][k]+g[i][j][k]);
l=max(l,f[i][j][k]);
} printf("%d",l); }