Given an array of integers, find the longest consecutive sequence, where a sequence is defined as being either (strictly) ascending, (strictly) descending, or all-equal.

836926 then has the longest sequence 369, which happens to be ascending. 241455556 has the longest sequence 5555, which happens to be all equal.

Please comment on the algorithm (correct? complexity?) and how it can be improved.

#include <iostream>
#include <vector>

int sign(int someInt)
{
    if (someInt > 0) { return 1; };
    if (someInt < 0) { return -1; };
    return 0;
}

bool isSequence(int a, int b, int c)
{
    if (sign(a - b) == sign(b - c))
    {
        return true;
    }

    return false;
}

void findSeq(const std::vector<int> &vect)
{
    int maxLength = 0;
    int startingIndex = 0;

    int currentLength = 2;
    int findIndex = 0;

    for (int i = 0; i < vect.size() - 2; i++)
    {

        if (isSequence(vect[i], vect[i + 1], vect[i + 2]))
        {
            currentLength++;
            if (currentLength > maxLength)
            {
                startingIndex = i - findIndex;
                maxLength = currentLength;
            }
            findIndex++;
        }

        else
        {
            findIndex = 0;
            currentLength = 2;
        }
    }

    for (int j = startingIndex; j < startingIndex + maxLength; j++)
    {
        std::cout << vect[j];
    }

}

The code is generally good and clear. I like the names you've used for your variables - it's very obvious what each does, with the possible exception of findIndex.

There's an issue with the problem statement (which might not be your fault): it doesn't say what to do if there's more than one "longest" sequence. In this code, it appears that we use the first match if there's another of the same length; it's worth writing a comment to be clear that this is what we want (and including such a case in the tests, so that we know if that changes).


isSequence is a bit more long-winded than it needs to be. This pattern is redundant:

if (condition)
    return true;
else
    return false;

It can always be replaced with

return condition;

In findSeq itself, we're doing pretty well. I get a compiler warning about comparing (signed) i against (unsigned) vect.size(); that's easily fixed by changing i to be a std::size_t instead of an int. Most of the other int variables would be better represented as std::size_t, too.

One thing we might want to do is to use iterators rather than indexes, to give us an opportunity to work with different collections in future. And instead of printing to std::cout, we might want to return the start and end iterators of the longest matching sequence. (If we do print the values, it's a good idea to separate them from each other, otherwise we can't tell 33,3 from 3,3,3, for example).

If we're using iterators, we'll want to remember the previous and ante-previous values, because we can't necessarily go back to them. Equivalently, we can remember the previous value and the direction of difference.

I don't know if this is beyond your current knowledge, but this is what I came up with when I followed my own suggestions, and took it a little further to work generically as a template:

#include <iterator>
#include <utility>

// return the sign of a-b (or the sign of a, if b is defaulted)
// result: -1 if a<b, 0 if a==b, +1 if a>b
template<typename T>
int compare(T a, T b = {})
{
    // This is a "clever" way of determining the sign.  Some
    // compilers recognise this idiom and reduce it to a single
    // instruction.
    return (a > b) - (a < b);
}

template<typename ForwardIterator>
std::pair<ForwardIterator,ForwardIterator>
findSeq(const ForwardIterator first, const ForwardIterator last)
{
    if (first == last) {
        // empty range -> empty result
        return { first, first };
    }

    auto best_start = first;
    auto best_end = first;
    std::size_t best_length = 0;

    auto current_start = first;
    auto previous = first;
    int current_direction = 0;
    std::size_t current_length = 0;

    auto const update_best = [&](ForwardIterator end){
        best_start = current_start;
        best_end = end;
        best_length = current_length;
    };

    for (auto it = std::next(first);  it != last;  ++it) {
        const auto new_direction = compare(*previous, *it);

        if (new_direction == current_direction) {
            ++current_length;
        } else {
            if (current_length > best_length) {
                update_best(it);
            }
            current_direction = new_direction;
            current_start = previous;
            current_length = 1;
        }

        previous = it;
    }

    if (current_length > best_length) {
        update_best(last);
    }

    return { best_start, best_end };
}

// provide an interface compatible with the original
template<typename Collection>
auto findSeq(const Collection& c)
{
    using std::begin;
    using std::end;

    return findSeq(begin(c), end(c));
}
#include <array>
#include <iostream>
#include <forward_list>
#include <vector>

template<typename ForwardIterator>
void printSeq(std::pair<ForwardIterator,ForwardIterator> range)
{
    auto [first,last] = range;
    for (auto it = first;  it != last;  ++it)
        std::cout << *it << ' ';
    std::cout << std::endl;
}

int main()
{
    printSeq(findSeq(std::vector{8,3,6,9,2,6,12}));
    printSeq(findSeq(std::array{-0.1, -0.2, -0.3, -0.4, 0.1, 0.2, 0.3, -1.0}));
    printSeq(findSeq(std::forward_list<std::string>{
                "foo", "bar", "bar", "bar", "baz", "quux"}));
}
  • 1
    Better to only update the solution on starting a new run, respectively at the end. Package it in a lambda, and it's clean and self-documenting. – Deduplicator Aug 9 at 15:29
  • It does look better with a name there, so I've edited. – Toby Speight Aug 9 at 15:51
  • 1
    This is beautiful, but obviously completely out of op’s skill level and therefore not very useful imo – downrep_nation Aug 9 at 16:44
  • 1
    @downrep - I did qualify with "I don't know if this is beyond your current knowledge" - I'm hoping that it's an answer to glean stuff from the beginning right now and to come back to later with more knowledge (and with the learning from other answers, too). – Toby Speight Aug 9 at 16:51

Your code is quite well-written, but in an old-fashioned, C-like way. With modern C++ you can be a lot more general and expressive.

Be more general

If you look at your code, you'll see that your function could also be invoked with arguments of a different type. For instance, if I change its signature to:

void findSeq(const std::vector<double> &vect);

it still works, even if I don't change anything inside the function. I could change the type more radically:

void findSeq(const std::string &vect);

and I still don't have to change anything else in your code.

That means you can be more general. Make your function a template:

template <typename Container>
void findSeq(const Container& container);

And you'll be able to use it on every type compatible with your code.

But you can be yet more general. Finding the longest subsequence is something I might not want to do on the whole container. I may want to specify the range inside which I need to find the longest subsequence. The canonical way to do it in C++ is to rely on iterators:

template <typename Iterator>
void findSeq(Iterator first, Iterator last);

For this, you'll need to change your code. It might prove hard if you're a beginner, but it's a good exercise.

Be more expressive

A good way to improve your code's expressiveness is to say what you're doing. You can do this with comments, with good variable names, and also by using named algorithms. There are a lot of them (and they're extremely well implemented) in the standard library (#include [<algorithm>][3]).

For instance there's an algorithm that looks for the position in a range where a predicate applied to two adjacent elements becomes true: std::adjacent_find. That comes handy when you want to detect a change of direction.

Lambda functions are another way to be more expressive. They're small, anonymous functions you can declare and define where they're used. They match very well with standard algorithms, which often come in the following form:

std::algorithm(Iterator first, Iterator last, Function fn);

So, here's a more modern implementation of your algorithm:

// taken from Toby Speight's answer
template<typename T>
int sign(T a, T b) {
    return (a > b) - (a < b);
}

template <typename Iterator>
auto lss(Iterator first, Iterator last) {
    if (std::distance(first, last) < 2) return std::make_pair(first, last);
    auto direction = sign(*first, *std::next(first));
    Iterator lss_begin = first, lss_end = first; 
    while (first != last) {
        auto change = std::adjacent_find(first, last, [&direction](auto l, auto r) {
            if (sign(l, r) != direction) {
                direction = sign(l, r);
                return true;
            }
            return false;
        });
        if (std::distance(lss_begin, lss_end) < std::distance(first, change)) {
            lss_begin = first;
            lss_end   = change;
        }
        first = change;
    }
    if (lss_end != last) ++lss_end;
    return std::make_pair(lss_begin, lss_end);
}
  • @Snowhawk: hence the if (lss_end != last) ++lss_end; before the return statement. – papagaga Aug 9 at 14:57
  • I really dislike the sign function’s name, because it isn’t the “sign” function, which has well-established semantics. Call it e.g. is_same_sign instead. – Konrad Rudolph Aug 9 at 15:10
  • 1
    If you go to iterators, mind the details. Your code is needlessly inefficient for anything but RandomaccessIterators. – Deduplicator Aug 9 at 15:17
  • @Konrad is_same_sign would be very misleading - that would imply (a < 0) == (b < 0) && (0 < a) == (0 < b) or equivalent. This function is a cmp() implementation (aka operator<=>()). – Toby Speight Aug 9 at 15:45
  • @TobySpeight Even better. Yes, is_same_sign is obviously wrong and entirely because I was misled by the original, wrong name. – Konrad Rudolph Aug 9 at 15:51

Think about what possible inputs your parameters can represent, like the empty set and sets smaller than expected.

    for (int i = 0; i < vect.size() - 2; i++) {

vect.size() returns an unsigned size type. If vect is smaller than the value you are subtracting, then your comparison will be i < huge number, leading to access violations.

        if (isSequence(vect[i], vect[i + 1], vect[i + 2])) {

Start at i = 2 and compare to size without the subtraction. The conditional here should do the subtraction, which won't invoke the modulus behavior as your checked values are guaranteed to exist.

        if (isSequence(vect[i-2], vect[i-1], vect[i])) {
        // Checks:           |          |         |
        //       [0,size-2) <┘          |         |
        //                  [1,size-1) <┘         |
        //                              [2,size) <┘

Overflow bug

You shouldn't do sign(a-b) because the value of a-b could overflow and give you the wrong sign value. For example, if a were 0x80000000 (a negative number) and b were 1, you would find a sign of 1 instead of -1. You should instead compare a against b directly. For example you could use the compare() function from Toby Speight's answer:

int compare(T a, T b = {})
{
    // This is a "clever" way of determining the sign.  Some
    // compilers recognise this idiom and reduce it to a single
    // instruction.
    return (a > b) - (a < b);
}

I recently answered a very similar question here. When I look at your code, it is very similar to my solution. The only suggestion for improvement I have for you is to try keeping three different variables for ascending/equal/descending, and updating them separately. However, I can't really say if that approach will be more efficient.

If I was really grasping at something to critique, I'd say that it'd be better if the function returned the smallest subsequence instead of printing it, but otherwise you've done a fantastic job!

I used the following driver functions to test your code.

#include <cstdlib>
#include <ctime>

void test()
{
   int size = std::rand() % 20;
   std::vector<int> arr(size);
   for (int i = 0; i < size; ++i )
   {
      arr[i] = std::rand() % 10;
   }

   std::cout << "Original sequence: ";
   for (int i = 0; i < size; ++i )
   {
      std::cout << arr[i];
   }
   std::cout << std::endl;

   findSeq(arr);
}

int main()
{
   std::srand(std::time(0));
   test();
   test();
   test();
}

I ran into couple of issues along the way.

  1. findSeq does not deal with the input gracefully if it has fewer than 3 elements. I would add the following check before the first for loop.

    if ( vect.size() < 2 )
    {
       return;
    }
    
  2. findSeq finds the longest sequence of 3 or more numbers. It does not find any sequence consisting of 2 numbers if that is the longest sequence. If you pass it an input consisting of 5, 1, 3, 0, 8, and 3, the function does not find any sequence that it considers it be the longest sequence. It's not clear from your post whether that is intentional.

The findIndex variable seems to be redundant. If you check this block of code:

    currentLength++;
    if (currentLength > maxLength)
    {
        startingIndex = i - findIndex;
        maxLength = currentLength;
    }
    findIndex++;

the only place where it's used is calculating the starting index. As both the currentLength and findIndex are also only incremented in this part, and start from 2 and 0 respectively, inside the if block it will always be true that findIndex == currentLength - 3.

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.