美文网首页
算法: 求一个矩阵中最大的二维矩阵(元素和最大)

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

作者: 谦业 | 来源:发表于2019-01-19 20:41 被阅读5次

    https://github.com/Alexchent/interview/blob/master/max_array.php

    /**

    • 求一个矩阵中最大的二维矩阵(元素和最大)。如:
    • 1 2 0 3 4
    • 2 3 4 5 1
    • 1 1 5 3 0
    • 中最大的是:
    • 4 5
    • 5 3
      */
    $arr = [
        [1,2,0,3,4],
        [2,3,4,5,1],
        [1,1,5,3,0]
    ];
    
    $res = find_max_array($arr);
    var_dump($res);
    
    /**
     * @param $arr
     * @return array
     * 时间复杂度 O(n²)
     */
    function find_max_array($arr)
    {
        $maxSum = 0;    //最大二维矩阵的元素和
        $x = 0; $y = 0; //最大二维矩阵的左上坐标点
        $row = count($arr) -1;
        $col = count($arr[0]) -1;
    
        for($i=0; $i<$row; $i++) {
            for ($j=0;$j< $col; $j++) {
                $tmp = $arr[$i][$j] + $arr[$i][$j+1] + $arr[$i+1][$j] + $arr[$i+1][$j+1];
                if ($tmp > $maxSum) {
                    $maxSum = $tmp;
                    $x = $i;
                    $y = $j;
                }
            }
        }
        return array(
            [$arr[$x][$y], $arr[$x][$y+1]],
            [$arr[$x+1][$y], $arr[$x+1][$y+1]],
        );
    }

    相关文章

      网友评论

          本文标题:算法: 求一个矩阵中最大的二维矩阵(元素和最大)

          本文链接:https://www.haomeiwen.com/subject/umnzdqtx.html