You are given a binary array nums
containing only 0s and 1s. Your task is to find the maximum number of consecutive 1s present in the array.
For example:
nums = [1, 1, 0, 1, 1, 1]
, the function should return 3
because the longest consecutive sequence of 1s is of length 3 (the last three elements).nums = [1, 0, 1, 1, 0, 1]
, the function should return 2
because the longest consecutive sequence of 1s is of length 2.nums = [0, 0, 0]
, the function should return 0
because there are no 1s.nums = [1, 1, 1, 1]
, the function should return 4
because all elements are 1s.nums = []
, the function should return 0
because the array is empty.Write a function that efficiently calculates the maximum number of consecutive 1s in a given binary array. Consider the time and space complexity of your solution.
The most straightforward approach is to iterate through the array and keep track of the current consecutive 1s and the maximum consecutive 1s seen so far. When we encounter a 0
, we reset the current consecutive count to 0
. Otherwise, we increment the count and update the maximum count if necessary.
Code (Python):
def find_max_consecutive_ones_naive(nums):
max_count = 0
current_count = 0
for num in nums:
if num == 1:
current_count += 1
max_count = max(max_count, current_count)
else:
current_count = 0
return max_count
max_count
and current_count
variables.The naive approach is already quite efficient, so there's not a significant optimization to be made in terms of time complexity. The optimal approach is essentially the same as the naive approach, focusing on code clarity and conciseness.
Code (Python):
def find_max_consecutive_ones_optimal(nums):
max_count = 0
current_count = 0
for num in nums:
if num == 1:
current_count += 1
else:
max_count = max(max_count, current_count)
current_count = 0
return max(max_count, current_count)
max_count
is 0.current_count
. After the loop, the max_count
will be updated with current_count
, effectively returning the length of the array.