CODEWITHSUNDEEP
c++algorithmstlsorting
JackNova
JackNova

Reputation: 3931

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

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

Upvotes: 6

Views: 2803

Answers (3)

Razvan
Razvan

Reputation: 10101

You need 4 indexes (begin, end, tmp_begin, tmp_end). Iterate through the original array using tmp_begin, tmp_end as the work indexes and each time you find a longer sorted sequence update begin and end indices.

To check that a subsequence is sorted, you have to check that element at i is greater than element at i-- for each pair of consecutive items in the subsequence.

In the end: print all the elements in the original array starting at begin and ending at end.

Upvotes: 5

Sergey Kalinichenko
Sergey Kalinichenko

Reputation: 727137

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.

Upvotes: 7

huseyin tugrul buyukisik
huseyin tugrul buyukisik

Reputation: 11926

for(int i=0;i<size_of_array;i++)
{
  iterate++;
  after=array[iterate];
  if(after>before) {current_counter++;} else {current_counter=0;}
  if(max_counter<current_counter) max_counter=current_counter;
  before=array[iterate];
}

printf(" maximum length=%i ",max_counter);

Upvotes: 1

Related Questions