Finding the length of the longest streak of ones in any array

Question

I need help reviewing my code snippet copied below. The below code counts the number of continuous ones in a given array of Size 11.

#define size 11
#define ONE 1
using namespace std;

#include <iostream> 
#include "stdio.h"

    int arr[11] = {1, 0, 1, -1, 0, 0, 1, 1,0, 1, 1};
        int sequence_count = 0; 
        int loop_count;
        bool continuity = true;
        for(loop_count = 0; loop_count<size; loop_count++)
        {
            if((arr[loop_count]&ONE) == ONE)
            {
                if(continuity)
                    sequence_count++;
                else
                {
                    continuity = true;
                    sequence_count++;
                }           
            }
            else
            {
                continuity = false; 
                sequence_count = 0;
            }
        }
        cout << sequence_count << endl;

Answer 1

I see a number of things that could help you improve your code.

Don't abuse using namespace std

Putting using namespace std at the top of every program is a bad habit that you'd do well to avoid.

Use only required #includes

The code has a line #include "stdio.h"s that is not needed. This clutters the code and makes it more difficult to read and understand. Only include files that are actually needed.

Provide main

It may just have been a cut and paste error, but this appears to be the contents of a main function, even though main does not appear.

Use appropriate names for constants

The constants size and ONE are a bit too generic and likely to be used elsewhere. In fact, this code won't even compile using a current version of gcc because of a name clash with size.

Prefer constexpr to old-style #define

Rather than using a #define for size the code could use a constexpr:

constexpr std::size_t ARRAY_SIZE = 11;

It doesn't make a lot of difference here, but generally the advantage is that the value has an associated type.

Declare variables as late as possible

Rather than using the old C-style of declaring all variables at the top of a function, use the modern C++-style and declare variables as late as possible. Doing so can sometimes help the compiler figure out register allocation, resulting in faster, smaller code.

Fix your formatting

There are inconsistent spaces at the beginning of lines, inconsistent indentation and inconsistent use of curly braces {}. Being consistent helps others read and understand your code.

Be careful with signed and unsigned

The code compares an int loop_count with the size of the array. Is the size of the array ever going to be a negative number? Probably not. Therefore, it would be better to declare loop_count to be of type std::size_t.

Fix the bugs

The description says that this code counts ones but the code includes this line:

if((arr[loop_count]&ONE) == ONE)

The use of the operator & in there is doing a binary "and" operation. That expression would be true if the value is -1 or 5 or any other odd number. What you probably really want is

if (arr[loop_count] == ONE)

Also, your program only counts the length of the last sequence of contiguous ones. If you want the maximum length, you'll have to save it.

Simplify your code

The code contains this sequence:

if(continuity)
    sequence_count++;
else
{
    continuity = true;
    sequence_count++;
}           

But it could be replaced with this simpler sequence:

sequence_count++;

And then the continuity variable isn't even needed.

An alternative

Here's the code as it might look with all of these suggestions applied:

#include <iostream> 

int main() 
{
    constexpr std::size_t ARRAY_SIZE {11};
    constexpr int target_value {1};

    int arr[ARRAY_SIZE] = {1, 0, 1, -1, 0, 1, 1, 1, 0, 1, 1};
    unsigned sequence_count = 0; 
    unsigned max_sequence = 0;
    for(std::size_t i = 0; i<ARRAY_SIZE; i++) {
        if (arr[i] == target_value) {
            if (++sequence_count > max_sequence) {
                max_sequence = sequence_count;
            }
        } else {
            sequence_count = 0;
        }
    }
    std::cout << max_sequence << std::endl;
}

Answer 2

Unnecessary inclusion

You never use anything from this included header:

#include "stdio.h"

Also, in C++ you should include the C++ front-end of C headers if available:

#include <cstdio>

Array index type

The natural type for array indices in C++ is std::size_t (or simply size_t in C) because it covers the whole range of possible index values on the current architecture.

size_t loop_count;

By extension you want the same type to count the length of the longest sequence

size_t sequence_count = 0;

Macro vs. function parameter

I don't find the declaration of ONE as a macro very useful. If you want your algorithm to work on sequences of arbitrary numbers you should wrap it in a function and supply that number as a function parameter.

size_t longest_sequence( const int *array, size_t array_length, int n )
{
  // ...
  return sequence_count;
}

Your code doesn't fit your description

Your code snipped returns the length of the last sequence of odd numbers – not the longest sequence of a ones! Let's see how we can fix it (including the aforementioned improvements):

#include <algorithm>
#include <iostream>

std::size_t longest_sequence( const int *array, std::size_t array_size, int n )
{
    std::size_t longest_sequence_length = 0,
        current_sequence_length = 0;

    for( std::size_t i = 0; i < array_size; i++)
    {
        if (array[i] == n)
        {
            current_sequence_length++;
        }
        else
        {
            if (current_sequence_length > longest_sequence_length)
                longest_sequence_length = current_sequence_length;

            current_sequence_length = 0;
        }
    }

    return std::max(current_sequence_length, longest_sequence_length);
}

int main()
{
    static const int arr[] = { 1, 0, 1, -1, 0, 0, 1, 1, 1, 0, 1, 1 };
    std::cout << longest_sequence(arr, sizeof(arr) / sizeof(*arr), 1) << std::endl;
}

Generalization

Since this is C++ you can trivially use a function template to generalize this algorithm to work with arbitrary container/iterator and element types:

#include <algorithm>
#include <array>
#include <iostream>

template <class Iterator, class T>
std::size_t longest_sequence( Iterator begin, Iterator end, T n )
{
    std::size_t longest_sequence_length = 0,
        current_sequence_length = 0;

    for( ; begin != end; ++begin)
    {
        if (*begin == n)
        {
            current_sequence_length++;
        }
        else
        {
            if (current_sequence_length > longest_sequence_length)
                longest_sequence_length = current_sequence_length;

            current_sequence_length = 0;
        }
    }

    return std::max(current_sequence_length, longest_sequence_length);
}


int main()
{
    static const std::array<int, 12> arr2 = { 1, 0, 1, -1, 0, 0, 1, 1, 1, 0, 1, 1 };
    std::cout << longest_sequence(arr2.begin(), arr2.end(), 1) << std::endl;
}