PHP练习-最大子序和


该问题最早于 1977 年提出,但是直到 1984 年才被发现了线性时间的最优解法。

题目要求

给定一个整数数组 arr,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。

function maxSubArray($arr) {
    if (!count($arr)) {
        return 0;
    }
    $dp[0] = $result = reset($arr);
    for ($i = 1; $i < count($arr); $i++) {
        $tmp = $dp[$i-1]+$arr[$i];
        $dp[$i] = $tmp > $arr[$i] ? $tmp : $arr[$i];
        $result = $dp[$i] > $result ? $dp[$i] : $result;
    }
    return $result;
}
$arr = [-2,8,-3,4,-1,2,1,-5,4];

echo maxSubArray($arr);

输出结果:11

上一篇 下一篇

评论

登录后可发表评论