第07周实验七最大子矩阵和问题

实验七动态规划最大子矩阵问题一、实验目的1、分析并掌握“最大子矩阵”问题的动态规划算法求解方法；2、运用动态规划算法解决实际问题加深对动态规划算法的理解和运用；二、实验环境WindowsXP以上版本的操作系统，VisualStudio2010编程环境。三、实验内容使用动态规划算法解决最大子矩阵问题，并能返回最大子矩阵的边界下标。问题描述：给定一个m行n列的整数矩阵A，试求A的一个子矩阵，使其各元素之和为最大。问题分析：用二维数组a[1:m][1:n]表示给定的m行n列的整数矩阵。子数组a[i1:i2][j1:j2]表示左上角和右下角行列坐标分别为(i1,j1)和(i2,j2)的子矩阵，其各元素之和记为：最大子矩阵问题的最优值为。如果用直接枚举的方法解最大子矩阵和问题，需要O(m^2n^2)时间。注意到，式中，，设，则容易看出，这正是一维情形的最大子段和问题。因此，借助最大子段和问题的动态规划算法MaxSum，可设计出最大子矩阵和动态规划算法参考：最大字段和动态规划算法：intMaxSum(intn,int*a){intsum=0,b=0;for(inti=1;i=n;i++){if(b0){b+=a[i];}else{b=a[i];}if(bsum){sum=b;}}returnsum;}