php - 求一个矩阵中4个方向的最高积

Question

我遇到了在 20x20 整数矩阵 上找到 4 个连续数字的最高乘积的挑战。

从文件中逐行读取数字，以空格分隔。

产品可横、竖、斜两个方向

我的“解决方案”给出了错误的答案。

编辑:我更新了代码以在没有文件输入的情况下工作并添加了示例数据；还修复了我在评论中指出的一个错误

$data = [
    [89,32,92,64,81,2,20,33,44,1,70,75,39,62,76,35,16,77,22,27],
    [53,11,6,95,41,51,31,59,8,23,19,13,61,91,48,69,84,52,66,24],
    [93,72,85,97,21,79,56,5,45,3,65,30,83,87,43,7,34,0,4,14],
    [29,17,49,9,82,90,55,67,15,63,54,94,12,28,96,37,58,98,86,78],
    [74,40,50,60,26,99,80,18,10,46,36,68,25,57,47,71,42,73,88,38],
    [50,22,6,26,18,53,52,5,46,2,89,77,83,48,4,58,45,28,84,81],
    [49,82,31,14,69,17,91,54,34,40,0,33,30,95,60,44,29,24,85,16],
    [27,11,76,39,15,86,92,74,99,59,94,12,55,57,38,96,47,32,78,75],
    [51,20,87,42,62,41,7,35,23,21,71,25,67,97,80,90,88,64,13,70],
    [19,9,56,43,68,93,65,98,36,3,61,63,10,72,8,73,1,66,79,37],
    [22,58,52,12,3,41,28,72,42,74,76,64,59,35,85,78,14,27,53,88],
    [46,80,5,96,7,68,61,69,67,34,36,40,82,26,75,50,29,91,10,2],
    [30,39,19,48,33,93,1,45,66,98,0,23,62,25,51,71,56,77,24,21],
    [79,87,94,60,8,32,13,65,4,92,73,9,31,37,17,84,15,90,86,20],
    [95,6,81,70,47,16,44,83,49,43,55,54,18,63,38,11,97,89,99,57],
    [95,78,64,58,7,17,53,28,74,86,6,12,54,85,21,94,16,69,25,68],
    [13,20,41,97,1,2,80,30,0,84,67,45,93,96,82,92,62,33,18,44],
    [60,77,31,70,76,36,59,38,15,3,91,46,65,73,49,11,8,35,5,52],
    [61,66,79,40,26,72,89,71,75,99,22,9,43,32,14,81,98,88,87,83],
    [10,4,23,19,56,57,51,47,50,27,90,63,42,29,24,55,48,37,39,34]
];

$matrix = [];
//maximums in possible directions
$maxes  = [0, 0, 0, 0];

//while ($line = trim(fgets(STDIN))) { 
while ($line = current($data)) {
    //the horizontal maxes can be calculated while loading
    //$array = explode(" ", $line);
    $array = $line;

    $hMax = array_product(array_slice($array, 0, 4));

    for ($i = 1; $i < (count($array)-4); $i++) {
        $max = array_product(array_slice($array, $i, 4));

        if($max > $hMax) {
            $hMax = $max;
        }
    }

    if ( $hMax > $maxes[0] ) {
        $maxes[0] = $hMax;
    }

    $matrix[] = $array;
    next($data);
}

// the last 3 rows can be skipped
for($i = 0; $i < (count($matrix)-4); $i++) {
    for ($j = 0; $j < (count($matrix[$i])-1); $j++) {

        $vMax  = 1;   // vertical
        $dlMax = 1;   // diagonal left
        $drMax = 1;   // diagonal rigth

        for ($k = 0; $k < 5; $k++) {
            $vMax  *= $matrix[$i + $k][$j];

            if ( $j < (count($matrix[$i]) - 4) ) {
                $drMax *= $matrix[$i + $k][$j + $k];
            }

            if ( $j > 3 ) {
                $dlMax *= $matrix[$i + $k][$j - $k];
            }
        }

        if ( $maxes[1] < $vMax )  $maxes[1] = $vMax;  // the index used to be 1 - my first mistake
        if ( $maxes[2] < $dlMax ) $maxes[2] = $dlMax; // the index used to be 1 - my first mistake
        if ( $maxes[3] < $drMax ) $maxes[3] = $drMax; // the index used to be 1 - my first mistake
    }
}

sort($maxes);
echo end($maxes).PHP_EOL;

我的方法哪里出了问题，如何才能加快速度？是否有任何数学技巧可以在这里应用(除了检查零)？

编辑:代码为当前数据给出的解决方案是4912231320是否正确？

Answer 1

我发现了 2 个主要错误，现在结果是合理的 67352832

出于这个原因，我认为它已解决，但如果有人想出一些可以简化或加快速度的数学技巧，我将放弃接受的答案。

第一个错误是 for ($k = 0; $k < 5; $k++) {

应该是 for ($k = 0; $k < 4; $k++) {

因为我们一次只计算 4 个数字，这就是结果比 10^8 大的原因

第二个是 if ( $j > 3 ) {

应该是 if ( $j > 2 ) {

现在将包含另一种对角线可能性