Reputation: 3931
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
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
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
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