Сложность: medium
Дан бинарный массив nums, верните максимальное количество последовательных единиц в массиве, если можно перевернуть не более одного нуля.
Пример:
Input: nums = [1,0,1,1,0]
Output: 4
Explanation:
- If we flip the first zero, nums becomes [1,1,1,1,0] and we have 4 consecutive ones.
- If we flip the second zero, nums becomes [1,0,1,1,1] and we have 3 consecutive ones.
The max number of consecutive ones is 4.
👨💻 Алгоритм:
1⃣Для каждого возможного начала последовательности в массиве nums начните считать количество нулей.
2⃣Для каждой последовательности проверяйте, сколько нулей содержится в ней. Если количество нулей не превышает одного, обновите максимальную длину последовательности единиц.
3⃣Продолжайте проверять все возможные последовательности в массиве, и верните максимальную длину последовательности единиц, удовлетворяющую условию.
😎 Решение:
class Solution {
function findMaxConsecutiveOnes($nums) {
$longestSequence = 0;
for ($left = 0; $left < count($nums); $left++) {
$numZeroes = 0;
for ($right = $left; $right < count($nums); $right++) {
if ($nums[$right] == 0) {
$numZeroes++;
}
if ($numZeroes <= 1) {
$longestSequence = max($longestSequence, $right - $left + 1);
}
}
}
return $longestSequence;
}
}Ставь 👍 и забирай 📚 Базу знаний