请教面试题：求矩阵中最大的二维矩阵

Question

题目描述

求一个矩阵中最大的二维矩阵（元素和最大），如：
1 2 0 3 4
2 3 4 5 1
1 1 5 3 0
中最大的是：
4 5
5 3
要求：（1）写出算法；（2）分析时间复杂度；

题目来源及自己的思路

最近面试遇到的一道题，我是面试PHP开发

Answer 1

/**

 * 求一个矩阵中最大的二维矩阵(元素和最大)

 * @param unknown $arr 二维矩阵

 * @param unknown $row 二维矩阵行数

 * @param unknown $col 二维矩阵列数

 * @return unknown[][]

 */
php

function test1($arr,$row,$col){
   $sum0 = 0;
   for ($i=0;$i<$row-1;$i++){
        for ($j=0;$j<$col-1;$j++){
            $sum1 = $arr[$i][$j]+$arr[$i][$j+1]+$arr[$i+1][$j]+$arr[$i+1][$j+1];
            if ($sum1 > $sum0){
                $l = $i;
                $m = $j;
                $sum0 = $sum1;
            }
        }
   }
$res= array(array($arr[$l][$m],$arr[$l][$m+1]),
array($arr[$l+1][$m],$arr[$l+1][$m+1]));
   return $res;
}
$arr = array(array(1,2,0,3,4),array(2,3,4,5,1),array(1,1,5,3,0));
print_r(test1($arr,3, 5));

javascript

            function test1(arr,row,col){
                   var sum0 = l = m = 0;
                   for (var i=0;i<row-1;i++){
                    for (var j=0;j<col-1;j++){
                        var sum1 = arr[i][j]+arr[i][j+1]+arr[i+1][j]+arr[i+1][j+1];
                        if (sum1 > sum0){
                            l = i;
                            m = j;
                            sum0 = sum1;
                        }
                    }
                   }
                var res = [[arr[l][m],arr[l][m+1]],arr[l+1][m],arr[l+1][m+1]];
                  return res;
            }
            var arr = [[1,2,0,3,4],[2,3,4,5,1],[1,1,5,3,0]];
            console.log(test1(arr,3, 5));

Answer 2

/**
 * @param $x 矩阵长度
 * @param $y 矩阵高度
 * @param $arr 矩阵数组
 * @return array 组成最大值的value
 */
function get_max_value($x,$y,$arr){
    $count=count($arr);
    if($x*$y!=$count){//判断是否是完整矩阵
        return false;
    }
    $list=array_chunk($arr,$x);//分割原数组
    $max=0;//初始化组成的最大值为0
    for($b1=1;$b1<$y;$b1++){//二维矩阵y轴坐标
        for($a1=0;$a1<$x-1;$a1++){//二维矩阵x轴坐标
            $s=$list[$b1-1][$a1]+$list[$b1-1][$a1+1]+$list[$b1][$a1]+$list[$b1][$a1+1];
            if($s>$max){
                $max=$s;
                unset($max_arr);
                $max_arr[]=[$list[$b1-1][$a1],$list[$b1-1][$a1+1],$list[$b1][$a1],$list[$b1][$a1+1]];
            }elseif($s==$max){//判断同时存在多个最大值
                $max_arr[]=[$list[$b1-1][$a1],$list[$b1-1][$a1+1],$list[$b1][$a1],$list[$b1][$a1+1]];
            }
        }
    }
    return $max_arr;
}
$arr=[1 ,2, 0, 3, 4,
2, 3, 4, 5, 1,
1, 1, 5, 3, 0];
print_r(get_max_value(5,3,$arr));