Brute Force Solution

The brute force solution involves iterating through the array and, for each element, checking the consecutive 1s starting from that element. We keep track of the maximum count found so far.

Algorithm

1. Initialize max_count to 0.
2. Iterate through the array from index i = 0 to n - 1.
3. For each index i, initialize current_count to 0.
4. While i is within the bounds of the array and nums[i] is 1, increment current_count and i.
5. Update max_count with the maximum of max_count and current_count.
6. Return max_count.

Code

def find_max_consecutive_ones_brute_force(nums):
    max_count = 0
    n = len(nums)
    for i in range(n):
        current_count = 0
        j = i
        while j < n and nums[j] == 1:
            current_count += 1
            j += 1
        max_count = max(max_count, current_count)
    return max_count

Time Complexity

O(n^2) in the worst case, where n is the length of the array. This is because, for each element, we might iterate through the rest of the array.

Space Complexity

O(1), as we only use a constant amount of extra space.

Optimal Solution

A more efficient solution involves iterating through the array only once, keeping track of the current consecutive 1s count and updating the maximum count as we go.

Algorithm

1. Initialize max_count to 0 and current_count to 0.
2. Iterate through the array from index i = 0 to n - 1.
3. If nums[i] is 1, increment current_count.
4. If nums[i] is 0, update max_count with the maximum of max_count and current_count, and reset current_count to 0.
5. After the loop, update max_count one last time to account for the case where the array ends with consecutive 1s.
6. Return max_count.

Code

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
    max_count = max(max_count, current_count)
    return max_count

Time Complexity

O(n), where n is the length of the array. This is because we iterate through the array only once.

Space Complexity

O(1), as we only use a constant amount of extra space.

Edge Cases

• Empty array: The algorithm should return 0.
• Array with all 0s: The algorithm should return 0.
• Array with all 1s: The algorithm should return the length of the array.

These edge cases are handled correctly by both the brute force and optimal solutions.