CODEWITHSUNDEEP
c++arrays
EdsellJ
EdsellJ

Reputation: 3

Longest Consecutive Sequence in Array C++

I have to create a function that will find the longest consecutive sequence of integers in an array.

The array is this:

{1,2,3,4,4,4,5,7,9,10}

Note: repeated numbers in a sequence are skipped.

Here is my code:

int longestSequence(const int arr[], int size)
{
  int currentSeq = 1;//set to 1 because all sequences are at least 1
  int maxSeq;

  for (int i = 1; i < size; i++)
  {
    if (arr[i] == arr[i-1]);//skip repeated numbers

    else if (arr[i-1] == (arr[i] - 1))//check if index is 1 greater than last
    {
      currentSeq++;
    }
    else //if not reset and hold last sequence value as max
      {
        maxSeq = currentSeq;
        currentSeq = 1;
      }
  }
  if (currentSeq > maxSeq) //if the last index of the array was last in the sequence
  {
    maxSeq = currentSeq;
  }

  return maxSeq;
}

My code keeps returning 2 for this array but obviously it should be 5.

Any help would be appreciated.

Upvotes: 0

Views: 2650

Answers (3)

tigertang
tigertang

Reputation: 457

#include <iostream>

void Log(int idx, int currentSeq, int maxSeq) {
  printf("current[%d] = %d, max[%d] = %d\n", idx, currentSeq, idx, maxSeq);
}

int LongestSequence(int* arr, int size) {
  int currentSeq = 1;
  int maxSeq = 1;  // max should be initialized as well
  Log(0, currentSeq, maxSeq);

  for (int i = 1; i < size; i++) {
    if (arr[i] == arr[i - 1]) {
    } else if (arr[i - 1] == (arr[i] - 1)) {
      currentSeq++;
    } else {
      currentSeq = 1;
    }
    // maxSeq should be updated in time, otherwise it would be tossed away
    maxSeq = std::max(maxSeq, currentSeq);
    Log(i, currentSeq, maxSeq);
  }

  return maxSeq;
}

int main() {
  int arr[] = {1, 2, 3, 4, 4, 4, 5, 7, 9, 10};
  std::cout << LongestSequence(arr, sizeof(arr) / sizeof(arr[0])) << std::endl;
}

Output:

current[0] = 1, max[0] = 1
current[1] = 2, max[1] = 2
current[2] = 3, max[2] = 3
current[3] = 4, max[3] = 4
current[4] = 4, max[4] = 4
current[5] = 4, max[5] = 4
current[6] = 5, max[6] = 5
current[7] = 1, max[7] = 5
current[8] = 1, max[8] = 5
current[9] = 2, max[9] = 5
5

Upvotes: 1

Matheus Rocha
Matheus Rocha

Reputation: 1204

You have 3 sequences in your array:

  • 1, 2, 3, 4, 4, 4, 5 which has 5 consecutive numbers.
  • 5, 7 which is not consecutive and will return 1.
  • 7, 9 which will also return one.
  • 9, 10 which has 2 consecutives and will return two.

In your loop you're doing this:

for (int i = 1; i < size; i++)
{
    if (arr[i] == arr[i-1]);//skip repeated numbers

    else if (arr[i-1] == (arr[i] - 1))//check if index is 1 greater than last
    {
        currentSeq++;
    }
    else //if not reset and hold last sequence value as max
    {
        maxSeq = currentSeq; // <-- You're resetting your maxSequence even if
                             // currentSeq is smaller.
        currentSeq = 1;
    }
}

Change your loop as following:

for (int i = 1; i < size; i++)
{
    if (arr[i] == arr[i-1])
        continue; //It is a good practice to skip the rest of the loop's 
                  //checks if you already know you're not gonna need them.
                  //The continue keyword skips only the current iteration of 
                  //the loop and improves intent readability.
    else if (arr[i-1] == (arr[i] - 1))//check if index is 1 greater than last
    {
        currentSeq++;
    }
    else //if not reset and hold last sequence value as max
    {
        currentSeq = 1; //This line stays.
                        //You only want to reset it under these specific conditions.
    }

    if (currentSeq > maxSeq) // Now you'll get the last sequence as well.
        maxSeq = currentSeq;
}

You can remove that check outside of the loop and go straight to the return. The last currentSeq will be properly registred if it is bigger than maxSeq.

Also, when I did this change I got a compile error because the new if (currentSeq > maxSeq) inside the loop tries to read maxSeq before it is ever set. So change the declaration of maxSeq to int maxSeq = 0.

With these changes I got the expected value of 5.

Upvotes: 1

Andreas Wenzel
Andreas Wenzel

Reputation: 24931

By running your program in a debugger with the sample array you provided, I determined that the variable currentSeq does indeed reach the value 5 and this value 5 is correctly written to maxSeq. However, later in the program, maxSeq gets overwritten by the value 1 and then 2.

Before overwriting maxSeq, you must determine whether it already contains a higher value than currentSeq. You already do this in one case, when you have reached the end of the array. But you don't do this in the other case.

For such a comparison to work, you must also initialize maxSeq, not just currentSeq. Otherwise, maxSeq may contain a very large number and always be larger than currentSeq.

Upvotes: 1

Related Questions