首页 > 代码库 > POJ 1050 To the Max 最详细的解题报告

POJ 1050 To the Max 最详细的解题报告

2024-07-24 23:03:22   221人阅读

题目来源：To the Max

题目大意：给定一个N*N的矩阵，求该矩阵中的某一个矩形，该矩形内各元素之和最大，即最大子矩阵问题。

 

解题方法：最大子序列之和的扩展

解题步骤：

1、定义一个N*N的矩阵state，state[j][k]用来存放矩阵的某行中第j到k个元素的最大值；

2、对于行如何处理呢？我们可以将第一行中的N个元素的所有组合的最大值存放在state中，如果有哪个值小于0，清零，因为它没有做任何贡献；定计算第二行时与第一行的值（全部大于等于0）进行累加，这样就完成了第一行与第二行的累加，即计算一个2行的子矩阵，依次类推。

 

具体算法（java版，可以直接运行）

 1 static int maxValue(int[][] array, int size) { 2         int max = Integer.MIN_VALUE; 3         int[][] state = new int[size][size]; 4         for (int i = 0; i < size; i++) {    // 第i行 5             for (int j = 0; j < size; j++) {// 第j列 6                 int sum = 0; 7                 for(int k=j;k<size;k++){// 第k列 8                     sum+=array[i][k]; //计算从i到k的值 9                     state[j][k] += sum;10                     if (state[j][k] > max) {11                         max = state[j][k];12                     }13                     if(state[j][k]<0){ //没有做贡献，清零14                         state[j][k]=0;15                     }16                 }17             }18         }19         return max;20     }21     public static void main(String[] args) {22         Scanner input = new Scanner(System.in);23         int size = input.nextInt();24         int[][] array = new int[size][size];25         for (int i = 0; i < size; i++) {26             for (int j = 0; j < size; j++) {27                 array[i][j] = input.nextInt();28             }29         }30         System.out.println(maxValue(array, size));31     }

 

为了方便理解，贴出state中值得变化情况：

数据：

0 -2 -7 0 
9 2 -6 2 
-4 1 -4 1 
-1 8 0 -2 

 

i=0时state中的值（由于第一行所有的值都不大于0，所以全部为0）：

0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0

i=1时state中的值：

9 11 5 7
0 2 0 0
0 0 0 0
0 0 0 2

i=2时state中的值：

5 8 0 1
0 3 0 0
0 0 0 0
0 0 0 3

i=3时state中的值：

4 15 7 6
0 11 8 6
0 0 0 0
0 0 0 1

 

如果有什么更好地解决方案，希望大家可以一起分享！

POJ 1050 To the Max 最详细的解题报告


联系
我们