PHP Max Double Slice Sum
function maxDoubleSliceSum(array $a): int
{
$size = count($a);
if ($size < 3) {
return 0;
}
$p1[1] = 0;
$p2[$size - 2] = 0;
for ($i = 2; $i < ($size - 1); $i++) {
$p1[$i] = max(0, $p1[$i - 1] + $a[$i - 1]);
$p2[$size - $i - 1] = max(0, $p2[$size - $i] + $a[$size - $i]);
}
$sum = $p1[1] + $p2[1];
for ($i = 1; $i < ($size - 1); $i++) {
$sum = max($sum, $p1[$i] + $p2[$i]);
}
return $sum;
}
This keeps the best sum ending on the left and starting on the right, then combines them around each middle position.