How do you find the maximum number of consecutive 1s in a binary array?
Short answer: Keep a running count of 1s, reset it to 0 on every 0, and remember the largest count seen. One pass, O(n) time, O(1) space.
#include <stddef.h>
size_t max_consecutive_ones(const int *arr, size_t n)
{
size_t count = 0, best = 0;
for (size_t i = 0; i < n; i++) {
if (arr[i] == 1) {
count++;
if (count > best) best = count;
} else {
count = 0;
}
}
return best;
}
/* {0,1,1,1,1,0,1,1,1,1,1,1,0,0,1,0} -> 6 */
Why update best inside the 1 branch: if the array ends with a run of 1s, there is no 0 afterwards to trigger a final comparison. Updating as you go avoids a separate check after the loop.
Bit-level version (popular in firmware interviews: longest run of 1s in a 32-bit register):
unsigned longest_run_of_ones(uint32_t x)
{
unsigned n = 0;
while (x) {
x &= x << 1; /* each step shortens every run by one */
n++;
}
return n;
}
/* 0b0111_1011 -> 4 */
Each x &= x << 1 removes the lowest 1 of every run, so the number of iterations equals the length of the longest run.
Follow-ups
- Flip at most one 0 to maximise the run: sliding window that allows at most one 0 inside; when a second 0 enters, move the left edge past the first 0.
- At most k zeros: the same window with a zero counter.
- Real use: finding the longest free block in an allocation bitmap.