How to Find the Maximum Consecutive Ones in an Array

Finding the maximum number of consecutive 1's in a binary array is a common problem that can be efficiently solved with a linear time algorithm. In this article, we will discuss an optimal approach to solve this problem.

Solution: Optimal Approach

This approach scans through the array once, keeping track of the current streak of consecutive 1's and updating the maximum streak encountered.

Implementation:

// Solution: Optimal Approach
// Time Complexity: O(n)
// Space Complexity: O(1)
int findMaxConsecutiveOnes(vector<int> &arr, int n)
{
    int maxOnes = 0;
    int count = 0;

    for (int i = 0; i < n; i++)
    {
        if (arr[i] == 1)
        {
            count++;

            if (count > maxOnes)
            {
                maxOnes = count;
            }
        }
        else
        {
            count = 0;
        }
    }

    return maxOnes;
}

Logic:

1. Initialize Counters: Use the maxOnes variable to store the maximum number of consecutive 1's found and count to store the current number of consecutive 1's.

2. Traverse the Array: Iterate through each element in the array. If the element is 1, increment count and update maxOnes if count exceeds maxOnes. If the element is not 1, reset count to 0.

3. Return Result: After the loop ends, return maxOnes as the result.

Time Complexity: O(n)

• Explanation: The array is traversed once, resulting in a linear time complexity.

Space Complexity: O(1)

• Explanation: The algorithm uses a constant amount of extra space for the counters.

Example:

• Input: arr = [1, 1, 0, 1, 1, 1]

• Output: 3

• Explanation: The maximum number of consecutive 1's is 3.

---

Edge Cases

• Empty Array: If the input array is empty, the function should return 0 as there are no elements.

• Array with No 1's: If the array contains only 0's, the function should return 0 as there are no 1's.

• Array with No 0's: If the array contains only 1's, the function should return the length of the array as all elements are consecutive 1's.

• Single Element Array: If the array contains only one element, which could be either 0 or 1. Then the function should return 0 if the element is 0 and 1 if the element is 1.

Additional Notes

• Efficiency: This approach is optimal with a time complexity of O(n) and space complexity of O(1), making it suitable for large arrays.

• Practicality: The algorithm is straightforward and easy to implement, making it a practical choice for solving this problem in real-world scenarios.

Conclusion

Finding the maximum number of consecutive 1's in a binary array can be efficiently solved using a linear scan approach. This method ensures optimal performance with minimal space usage, making it a robust solution for various applications.

---