半大学出版社 最大子矩阵和问题 给定一个m行n列的整数矩阵a,试求矩阵a的一个子矩阵,使其 各元素之和为最大 记s(12,八,12)=∑∑ i=il j=jl 最大子矩阵和问题的最优值为Xmn2,八2) 由于mXm812,几1,12)=mXn{X2(,2,八,12)=mm2) 其中,12)=mB(121,12)=m∑∑ 设小4,则似2)=m 由于解最大子段和问题的动态规划算法需要时间o(n),故算 法的双重for循环需要计算时间O(m2n)7 最大子矩阵和问题 记 最大子矩阵和问题的最优值为 由于 其中， 设 ，则 给定一个m行n列的整数矩阵a，试求矩阵a的一个子矩阵，使其 各元素之和为最大。 = = = 2 1 2 1 ( 1, 2, 1, 2) [ ][ ] i i i j j j s i i j j a i j max ( 1, 2, 1, 2) 1 1 2 1 1 2 s i i j j j j n i i m       max ( 1, 2, 1, 2) max { max ( 1, 2, 1, 2)} max ( 1, 2) 1 1 2 1 1 2 1 1 2 1 1 2 1 1 2 s i i j j s i i j j t i i i i m j j n i i m j j n i i m                = = = =       = = 2 1 2 1 1 1 2 1 1 2 ( 1, 2) max ( 1, 2, 1, 2) max [ ][ ] j j j i i i j j n j j n t i i s i i j j a i j = = 2 1 [ ] [ ][ ] i i i b j a i j =    = 2 1 1 1 2 ( 1, 2) max [ ] j j j j j n t i i b j 由于解最大子段和问题的动态规划算法需要时间O(n)，故算 法的双重for循环需要计算时间O(m2n)