Get length of the longest sequence of numbers with the same sign

Question

I need to get length of the longest sequence of numbers with the same sign. Assumes that zero is positive. For example:

{10, 1, 4, 0, -7, 2, -8, 4, -2, 0} → 4
{0, 1, 2, 3, -2, -4, 0}  → 4
{1, -2, 0, -1} → 1

I wrote a function:

unsigned getLongestSameSignSequenceLength(std::vector<int> const& a)
{
    unsigned maxlen = 1;

/* Assumes that zero is positive. */
#define SIGN(a) (a >= 0)

    for (size_t i = 1, len = 1; i < a.size(); i++, len++) {
        if (SIGN(a[i]) != SIGN(a[i - 1])) {
            maxlen = std::max(maxlen, len);
            len = 0;
        } else {
            if (i == a.size() - 1)
                return std::max(maxlen, len + 1);
        }
    }

#undef SIGN

    return maxlen;
}

Can you please give me tips to improve my code?

Answer 1

A small portability bug: std::size_t is in the std namespace, assuming it's declared by including <cstddef> (recommended).

No unit tests are included, but I'd expect one that tests that the result is zero when the input collection is empty. We need to initialize maxlen to zero for that test to pass.

When comparing consecutive elements of a collection, always consider using std::adjacent_find(). With a suitable predicate function, we can find changes from negative to non-negative and vice versa without needing to code our own loop or do any indexing.

(More advanced) Consider making your algorithm generic, templated on an iterator type, so that it can be applied to any collection (or even to an input stream directly).

Here's a version that applies all of these suggestions (and some from other answers that I've not repeated above):

#include <algorithm>
#include <cmath>
#include <cstddef>
#include <iterator>

template<typename ForwardIt>
std::size_t getLongestSameSignSequenceLength(ForwardIt first, ForwardIt last)
{
    auto const signdiff =
        [](auto a, auto b){ return std::signbit(a) != std::signbit(b); };

    std::size_t maxlen = 0;

    while (first != last) {
        ForwardIt change = std::adjacent_find(first, last, signdiff);
        if (change != last) { ++change; }

        std::size_t len = std::distance(first, change);
        if (len > maxlen) { maxlen = len; }

        first = change;
    }

    return maxlen;
}

// tests:

#include <vector>

int main()
{
    struct testcase { std::size_t expected; std::vector<int> inputs; };
    std::vector<testcase> tests
        {
         {0, {}},
         {1, {1}},
         {1, {1, -2}},
         {1, {1, -2,  3}},
         {1, {-1, 2, -3}},
         {2, {1,  2}},
         {2, {1,  2, -3}},
         {2, {-1, -2, 3}},
         {2, {-1, 2,  3}},
         {2, {-1, 2,  3, -4}},
        };

    int failures = 0;
    for (auto const& [e, v]: tests) {
        failures += getLongestSameSignSequenceLength(v.begin(), v.end()) != e;
    }

    return failures;
}

Answer 2

I would raise at least the following points:

• Instead of taking as input an std::vector, you could rather take two iterators pointing to the beginning and end of a range. In this way, you can also nicely operate on ranges.

• To avoid all sorts of evil associated with macros, you can use a lambda function here instead. So just define e.g., const auto sign = [](int v) { return v >= 0; }; and use this instead of SIGN.

• You might run into compilation problems with std::max and its arguments being unsigned and size_t (happens on MSVC'15 at least). So you should use the same type for both arguments.

Answer 3

Since this is C++ and not C, macros should generally be avoided. Define a function or create a named lambda expression might be better.

If you are going to use a macro define it before the function (outside the function) and undefine it after the function.

The code isn't using most of what a container class provides, there is no use of iterators, and the vector is being treated like a C language array.