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

算法开销O(NLogN)

代码:

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

function maxSubSum($arr,$left,$right){
    $maxLeftSum=0;//左边最大序列和
    $maxRightSum=0;//右边最大序列和
    $maxLeftBorderSum=0;//中左最大序列和
    $maxRightBorderSum=0;//中右最大序列和
    $leftBorderSum=0;//作为 转换变量
    $rightBorderSum=0;//作为 转换变量
    if($left==$right){
        if($arr[$left]>0){
            return $arr[$left];
        }else{
            return 0;
        }
    }
    $center= (int)(($left+$right)/2);
    $maxLeftSum=maxSubSum($arr,$left,$center);
    $maxRightSum=maxSubSum($arr,$center+1,$right);

    for ($i=$center;$i>=$left;$i--){
        $leftBorderSum+=$arr[$i];
        if($leftBorderSum>$maxLeftBorderSum){
            $maxLeftBorderSum=$leftBorderSum;
        }
    }

    for ($i=$center+1;$i<=$right;$i++){
        $rightBorderSum+=$arr[$i];
        if($rightBorderSum>$maxRightBorderSum){
            $maxRightBorderSum=$rightBorderSum;
        }
    }

    return max($maxLeftSum,$maxRightSum,$maxLeftBorderSum+$maxRightBorderSum);
}

function maxSubsequenceSum($arr,$n){
    return maxSubSum($arr,0,$n-1);
}

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

输出:

20
遇到问题?