Задача: 487. Max Consecutive Ones II
Дан бинарный массив 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 {
fun findMaxConsecutiveOnes(nums: IntArray): Int {
var longestSequence = 0
for (left in nums.indices) {
var numZeroes = 0
for (right in left until nums.size) {
if (nums[right] == 0) {
numZeroes++
}
if (numZeroes <= 1) {
longestSequence = maxOf(longestSequence, right - left + 1)
}
}
}
return longestSequence
}
}👉Новости 👉База вопросов