Problem Statement

Given an array that contains only 1 and 0 return the count of maximum consecutive ones in the array.

Examples

Example 1:

Input: array = {1, 0, 1, 1, 1, 0}

Output: 3

There are three consecutive 1's.

Approach

We maintain a variable count that keeps a track of the number of consecutive 1's while traversing the array.

We start traversing from the beginning of the array.

Code

#include <iostream>
#include <vector>

using namespace std;

int maxConsecutiveOnes(const vector<int>& nums) {
    int maxCount = 0;
    int currentCount = 0;

    for (int num : nums) {
        if (num == 1) {
            // Increment current count for consecutive ones
            currentCount++;
        } else {
            // Update max count if current count is greater
            if (currentCount > maxCount) {
                maxCount = currentCount;
            }
            // Reset current count for consecutive ones
            currentCount = 0;
        }
    }

    // Update max count if current count exceeds previous max
    if (currentCount > maxCount) {
        maxCount = currentCount;
    }

    return maxCount;
}

int main() {
    vector<int> nums = {1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1};
    int maxConsecutive = maxConsecutiveOnes(nums);
    cout << "Maximum consecutive ones: " << maxConsecutive << endl;
    return 0;
}

// Output
Maximum consecutive ones: 4

Complexity Analysis

Time Complexity:

• Loop Through the array: This loop contributes O(n) time complexity, where n is the number of elements in the array.
• Updating Maximum Count: Within the loop, there are constant-time operations for updating the current count and comparing it with the maximum count. These operations do not significantly affect the overall time complexity.
• Overall: Since the dominant operation is the single loop through the array, the time complexity of this solution is O(n)

Space Complexity: O(1) because no extra space is used.