PHP Flags
function flags(array $a)
{
$size = count($a);
$peaks = [false];
$next = [];
for ($i = 1; $i < $size; $i++) {
$peaks[$i] = $a[$i - 1] < $a[$i] && $a[$i] > ($a[$i + 1] ?? 0);
}
$next[$size - 1] = -1;
for ($i = $size - 2; $i >= 0; $i--) {
$next[$i] = $peaks[$i] ? $i : $next[$i + 1];
}
$i = 1;
$result = 0;
while ($i * ($i - 1) <= $size) {
$pos = 0;
$num = 0;
while ($pos < $size && $num < $i) {
$pos = $next[$pos];
if ($pos === -1) {
break;
}
++$num;
$pos += $i;
}
$i++;
$result = max($result, $num);
}
return $result;
}
This finds all peaks first, then checks how many flags can be placed while keeping the required distance.