php - 前缀和通过在数组中移动 m 步找到最大收集值

Question

我正在尝试在 php 中实现前缀和逻辑 codility .

这是我要解决的问题:

You are given a non-empty, zero-indexed array A of n (1 ¬ n ¬ 100 000) integers a0, a1, . . . , an−1 (0 ¬ ai ¬ 1 000). This array represents number of mushrooms growing on the consecutive spots along a road. You are also given integers k and m (0 ¬ k, m < n). A mushroom picker is at spot number k on the road and should perform m moves. In one move she moves to an adjacent spot. She collects all the mushrooms growing on spots she visits. The goal is to calculate the maximum number of mushrooms that the mushroom picker can collect in m moves. For example, consider array A such that: [2, 3, 7, 5, 1, 3, 9]

The mushroom picker starts at spot k = 4 and should perform m = 6 moves. She might move to spots 3, 2, 3, 4, 5, 6 and thereby collect 1 + 5 + 7 + 3 + 9 = 25 mushrooms. This is the maximal number of mushrooms she can collect.

这是我的 php 代码:

$P = [2, 3, 7, 5, 1, 3, 9]; // mushroom count per position
$k = 4; // start position of picker
$m = 6; // moves allowed
$n = count($P);
$result = 0;
$pref = $this->getPrefixSum($P);

$leftBoundary = min($m, $k);

for ($i=0; $i < $leftBoundary; $i++) { 
        $leftPos  = $k - $i;
        $rightPos = min($n - 1, max($k, $k + $m - 2 * $i));
        $result   = max($result, $pref[$rightPos] - $pref[$leftPos]);
    }

    $rightBoundary = min($m + 1, $n - $k);
    for ($i=0; $i < $rightBoundary ; $i++) { 
        $rightPos = $k + $i;
        $leftPos  = max(0, min($k, $k - ($m - 2 * $i)));
        $result   = max($result, $pref[$rightPos] - $pref[$leftPos]);
    }

function getPrefixSum($A)
{
    $prefixSums = array();
    $prefixSums[0] = $A[0];
    for ($i=1; $i < count($A); $i++) { 
        $prefixSums[$i] = $prefixSums[$i - 1] + $A[$i];
    }
    return $prefixSums;
}

不幸的是，我得到的结果仅为 19(预期答案为 25)。你们知道我是否遗漏了什么吗？任何帮助将不胜感激。

Answer 1

翻译示例代码时存在多个错误。主要问题是您的 prefixSum 函数生成的数组的索引比示例代码少一个。这是一个比较:

# them
[0, 2, 5, 12, 17, 18, 21, 30] 

# you
Array
(
    [0] => 2
    [1] => 5
    [2] => 12
    [3] => 17
    [4] => 18
    [5] => 21
    [6] => 30
)

否则，您将省略它们包含的操作，因此我将在下面的工作代码中突出显示它们:

function getPrefixSum($A) {
    $prefixSums = [0];
                # ^^^

    for ($i = 1; $i < count($A) + 1; $i++) { 
                             # ^^^^
        $prefixSums[$i] = $prefixSums[$i-1] + $A[$i-1];
                                                 # ^^
    }

    return $prefixSums;
}

$P = [2, 3, 7, 5, 1, 3, 9]; // mushroom count per position
$k = 4; // start position of picker
$m = 6; // moves allowed
$n = count($P);
$result = 0;
$pref = getPrefixSum($P);

$leftBoundary = min($m, $k) + 1;
                         # ^^^^

for ($i = 0; $i < $leftBoundary; $i++) { 
    $leftPos = $k - $i;
    $rightPos = min($n - 1, max($k, $k + $m - 2 * $i));
    $result = max($result, $pref[$rightPos+1] - $pref[$leftPos]);
                                        # ^^
}

$rightBoundary = min($m + 1, $n - $k);

for ($i = 0; $i < $rightBoundary; $i++) { 
    $rightPos = $k + $i;
    $leftPos = max(0, min($k, $k - ($m - 2 * $i)));
    $result = max($result, $pref[$rightPos+1] - $pref[$leftPos]); 
                                        # ^^
}

echo "$result\n";

输出:

25

Try it out .