动态规划——最大长方体问题

长方体问题"/>

动态规划——最大长方体问题

最大长方体问题

先从1维开始考虑：

遍历整个一维数组，设 d p [ i ] dp[i] dp[i]为前 i i i个数的最大和，如果某个数 n u m s [ i ] < 0 nums[i]<0 nums[i]<0， d p [ i ] = d p [ i − 1 ] dp[i]=dp[i-1] dp[i]=dp[i−1],否则为 d p [ i − 1 ] + n u m s [ i ] dp[i-1]+nums[i] dp[i−1]+nums[i].

再考虑二维：

将二维数组抽象为多个一维数组，遍历调用一维的求最大和的方法

最后考虑三维：

将三位数组抽象为多个二维数组，遍历调用二维的求最大和的方法

代码如下

# -*- coding: utf-8 -*-
"""
Created on Mon Apr 11 19:25:27 2022@author: skyoung
"""def maxSum1D(nums,n):sums=0temp=[0]*(n+1)for i in range(1,n+1):if nums[i]>=0:temp[i]=temp[i-1]+nums[i]else:temp[i]=temp[i-1]if temp[i]>sums:sums=temp[i]return sumsdef maxSum2D(nums,n,m):sums=0for i in range(1,n+1):temp=[0]*(m+1)j=iwhile j<=n:for k in range(1,m+1):temp[k]+=nums[j][k]tempSum=maxSum1D(temp,m)if tempSum>sums:sums=tempSumj+=1return sumsdef maxSum3D(nums,n,m,p):sums=0for i in range(1,p+1):temp=[[0]*(n+1) for _ in range(m+1)]j=iwhile j<=p:for k in range(1,m+1):for l in range(1,n+1):temp[k][l]+=nums[j][k][l]tempSum=maxSum2D(temp,n,m)if tempSum>sums:sums=tempSumj+=1return sums## 先读入数据
import re
fin=open('input.txt','r')
data=(fin.readline().strip(' '))
m,n,p=(re.findall("\d+",data))
m=int(m)
n=int(n)
p=int(p)
#读入m,n,p
dp=[[[0]*(p+1) for _ in range(n+1)] for _ in range(m+1)]
for i in range(1,m+1):for j in range(1,n+1):data=(fin.readline().strip(' '))data=(re.findall("\-?\d+",data))for k in range(1,p+1):dp[i][j][k]=int(data[k-1])
fin.close() 
print('the answer is ',maxSum3D(dp,n,p,m))

空间复杂度 O ( m ∗ n ∗ p ) O(m*n*p) O(m∗n∗p)

时间复杂度 O ( m ∗ m ∗ n ∗ n ∗ p ) O(m*m*n*n*p) O(m∗m∗n∗n∗p)