动态规划练习题：POJ 1050

给定正整数的二维数组，子矩形是位于整个数组中的大小为1 * 1或更大的任何连续子阵列。矩形的总和是该矩形中所有元素的总和。在这个问题中，具有最大和的子矩形被称为最大子矩形。 
作为示例，阵列的最大子矩形： 

0 -2 -7 0 
9 2 -6 2 
-4 1 -4 1 
-1 8 0 -2 
在左下角： 

9 2 
-4 1 
-1 8 

，总和为15。

import java.util.Scanner;
public class Main{
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int[][] arr=new int[n][n];
for(int i=0;i<n;i++) {
for(int j=0;j<n;j++) {
arr[i][j]=sc.nextInt();
}
}
int[][][] dp=new int[n][n][n];
int max=0;
for(int j=0;j<n;j++) {
int sum=0;
for(int k=j;k<n;k++) {
sum+=arr[0][k];
dp[0][j][k]=sum;
}
}
for(int i=1;i<n;i++) {
for(int j=0;j<n;j++) {
int sum=0;
for(int k=j;k<n;k++) {
sum+=arr[i][k];
dp[i][j][k]=Math.max(dp[i-1][j][k]+sum,sum);
max=Math.max(max, dp[i][j][k]);
}
}
}
System.out.println(max);
sc.close();
}
}

最后

以上就是平常手套为你收集整理的动态规划练习题：POJ 1050的全部内容，希望文章能够帮你解决动态规划练习题：POJ 1050所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。