如何实现三维动态规划？

可在一维数组中找出最大和子段
可在二维数组中找出最大和子矩阵
那么如何在三维数组中找出最大和子立方体

1.一维找出最大子和段方法如下
int thissum=0,maxsum=0;
for (int q=0;q {
thissum+=a[q];
thissum=max(thissum,0);
maxsum=max(thissum,maxsum);
}
最后maxsum就是答案了 复杂度为o(n) （看不懂这段的再追问吧）
2.二维其实是基于一维的查找方法，通过枚举列、然后对行进行动态规划，当然要加上前缀和的优化(即s[i][j]=a[0][j]+....+a[i][j]) 复杂度o(n^2*m）;
for (int q=1;q<=n;q++)
for (int p=q;p<=n;p++)
{
thissum=0;
for (int i=0;i {
thissum+=s[p][i]-s[q-1][i];
thissum=max(thissum,0);
maxsum=max(thissum,maxsum);
}
}
3.三维的思路依旧，枚举长高、对宽进行动态规划，加上前缀和优化，复杂度o(h^2*m^2*n）
for (q=1;q<=h;q++)
for (i=1;i<=m;i++)
for (j=1;j<=n;j++)
{
scanf("%d",&k);
s[q][i][j]=s[q][i-1][j]+k;
}

for (q=1;q<=h;q++)
for (i=1;i<=m;i++)
for (j=1;j<=n;j++)
s[q][i][j]+=s[q-1][i][j];

for (q=1;q<=h;q++)
for (p=q;p<=h;p++)
for (i=1;i<=m;i++)
for (j=i;j<=m;j++)
{
thissum=0;
for (k=1;k<=n;k++)
{
thissum+=s[p][j][k]-s[q-1][j][k]-s[p][i-1][k]+s[q-1][i-1][k];
if (thissum>maxsum) maxsum=thissum;
if (thissum<0) thissum=0;
}
}

另外，oj上有道题目似乎就是求这个的 好像是叫吃西瓜来着 你可以搜一下...

3dmark