Задача: 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 {
public:
int findMaxConsecutiveOnes(vector<int>& nums) {
int longestSequence = 0;
for (int left = 0; left < nums.size(); ++left) {
int numZeroes = 0;
for (int right = left; right < nums.size(); ++right) {
if (nums[right] == 0) {
numZeroes++;
}
if (numZeroes <= 1) {
longestSequence = max(longestSequence, right - left + 1);
}
}
}
return longestSequence;
}
};👉Новости 👉База вопросов