Find the longest run of sequential integers in a vector

Question

I have a routine that returns a list of integers as a vector.

Those integers come from groups of sequential numbers; for example, it may look like this:

vector = 6 7 8 12 13 14 15 26 27 28 29 30 55 56

Note that above, there are four 'runs' of numbers (6-8, 12-15, 26-30 & 55-56). What I'd like to do is forward the longest 'run' of numbers to a new vector. In this case, that would be the 26-30 run, so I'd like to produce:

newVector = 26 27 28 29 30

This calculation has to be performed many, many times on various vectors, so the more efficiently I can do this the better! Any wisdom would be gratefully received.

Answer 1

You can try this:

v = [ 6 7 8 12 13 14 15 26 27 28 29 30 55 56];

x = [0 cumsum(diff(v)~=1)];

v(x==mode(x))

This results in

ans =

    26    27    28    29    30

Answer 2

Here is a solution to get the ball rolling . . .

vector = [6 7 8 12 13 14 15 26 27 28 29 30 55 56]
d = [diff(vector) 0]


maxSequence = 0;
maxSequenceIdx = 0;
lastIdx = 1;

while lastIdx~=find(d~=1, 1, 'last')

    idx = find(d~=1, 1);
    if idx-lastIdx > maxSequence
        maxSequence = idx-lastIdx;
        maxSequenceIdx = lastIdx;
    end

    d(idx) = 1;

    lastIdx=idx;
end

output = vector(1+maxSequenceIdx:maxSequenceIdx+maxSequence)

In this example, the diff command is used to find consecutive numbers. When numbers are consecutive, the difference is 1. A while loop is then used to find the longest group of ones, and the index of this consecutive group is stored. However, I'm confident that this could be optimised further.

Answer 3

Without loops using diff:

vector = [6 7 8 12 13 14 15 26 27 28 29 30 55 56];

seqGroups = [1 find([1 diff(vector)]~=1) numel(vector)+1]; % beginning of group
[~, groupIdx] = max( diff(seqGroups));                     % bigger group index

output = vector( seqGroups(groupIdx):seqGroups(groupIdx+1)-1)

output vector is

ans = 

    26    27    28    29    30

Answer 4

Without loops - should be faster

temp = find ( ([(vector(2:end) - vector(1:end-1))==1 0])==0);
[len,ind]=max(temp(2:end)-temp(1:end-1));
vec_out =  vector(temp(ind)+1:temp(ind)+len)