数据结构-最大子序列和O(N) 可刷新运行 刷新

算法开销O(N)

代码:

$arr = [-2, 11, -4, 13, -5, -2];

function maxSubsequenceSum($arr, $n)
{
    $maxSum = 0;
    $thisSum = 0;

    for ($i = 0; $i < $n; $i++) {
        $thisSum += $arr[$i];
        if ($thisSum > $maxSum) {
            $maxSum = $thisSum;
        } else if ($thisSum < 0) {
            $thisSum = 0;
        }
    }
    return $maxSum;
}

echo maxSubsequenceSum($arr, 6) . "\n";
echo "<img src='https://jc91715.top/storage/app/blog/dmI4T6DYT3.png'/>";

输出:

20
遇到问题?