I create Sequence elements telling the FIRST and LAST element of the sequence, sorting them in a linked list.

For each input number:

- scroll the sequence list as far as the input is LESS than next sequence (or end of list) (while).
- check if the input is in the current sequence (continue)
- if extends both, merge
- else if extends one, update bound
- else there's no extension at all, so add new sequence (one element)

In the meanwhile:

At every sequence change update maxSeqLength

```
class Solution {
struct Sequence {
int first;
int last;
Sequence* next;
Sequence(int aFirst, int aLast)
: first(aFirst), last(aLast), next(NULL) {}
~Sequence() { if (next) delete next; }
};
public:
int longestConsecutive(vector<int> &num) {
int maxSeqLength = 0;
vector<int>::iterator it = num.begin();
int minInt = std::numeric_limits<int>::min();
Sequence dummyHead(minInt,minInt);
while(it != num.end())
{
Sequence* head = &dummyHead;
int val = *it++;
// Scroll list when val > next_sequence_first
while (head->next && (val > head->next->first))
{
head = head->next;
}
// Skip if already contained in next or previous sequence
if ((head->next && val == head->next->first) || (val <= head->last) )
{
continue;
}
// Check if expands previous sequence (high bound) or next sequence (low bound)
bool bExpandPrevious = (head->last == val - 1 );
bool bExpandNext = (head->next && (head->next->first == val + 1));
// it can happen we've got a value that merges two sequences
if (bExpandPrevious && bExpandNext)
{
//Merge
Sequence* pTemp = head->next;
head->next = head->next->next;
head->last = pTemp->last;
pTemp->next = NULL;
delete pTemp;
maxSeqLength = std::max(maxSeqLength, head->last - head->first + 1);
}
else if (bExpandPrevious) // or expands previous only
{
//Update last
head->last = val;
maxSeqLength = std::max(maxSeqLength, head->last - head->first + 1);
}
else if (bExpandNext) // or expands last only
{
// Update first
head->next->first = val;
maxSeqLength = std::max(maxSeqLength, head->next->last - head->next->first + 1);
}
else // or it's a brand new sequence (of 1 element!)
{
// insert in between
Sequence* pTemp = head->next;
head->next = new Sequence(val, val);
head->next->next = pTemp;
maxSeqLength = std::max(maxSeqLength, head->next->last - head->next->first + 1);
}
}
return maxSeqLength;
}
};
```