simpest way to get the longest sequence of sorted elements from a given unsorted integer vector in c++

Question

I have an unsorted array and need to extract the longest sequence of sorted elements. For instance

A = 2,4,1,7,4,5,0,8,65,4,2,34

here 0,8,65 is my target sequence

I need to keep track of the index where this sequence starts

Answer 1

You can do it in linear time O(N) with this algorithm: construct vector len of the same size N as the original vector, such that len[i] contains the length of the longest consecutive ascending run to which element seq[i] belongs.

The value of len[i] can be calculated as follows:

len[0] = 1;
for (int i = 1 ; i != N ; i++) {
    len[i] = seq[i-1] >= seq[i] ? 1 : len[i-1]+1;
}

With len in hand, find the index of max(len) element. This is the last element of your run. Track back to len[j] == 1 to find the initial element of the run.

seq    len
---    ---
  2      1
  4      2
  1      1
  7      2
  4      1
  5      2
  0      1
  8      2
 65      3 << MAX
  4      1
  2      1
 34      2

Note that at each step of the algorithm you need only the element len[i-1] to calculate len, so you can optimize for constant space by dropping vector representation of len and keeping the prior one, the max_len, and max_len_index.

Here is this algorithm optimized for constant space. Variable len represents len[i-1] from the linear-space algorithm.

int len = 1, pos = 0, maxlen = 1, current_start = 0;
for (int i = 1 ; i < seq.size() ; i++) {
    if (seq[i] > seq[i-1]) {
        len++;
        if (len > maxlen) {
            maxlen = len;
            pos = current_start;
        }
    } else {
        len = 1;
        current_start = i;
    }
}

Here is a link to this program on ideone.