find the longest monotonically increasing subsequence of a sequence of n numbers?

I have algorithm of the longest monotonically increasing subsequence of a sequence of n numbers

Let S[1]S[2]S[3]...S[n] be the input sequence.

Let L[i] , 1<=i <= n, be the length of the longest monotonically increasing subsequence of the first i letters S[1]S[2]...S[i] such that the last letter of the subsequence is S[i].

Let P[i] be the position of the letter before S[i] in the longest subsequence of the first i letters such that the last letter is S[i].

T is the resulting subsequence.

Algorithm

1. for i=1 to n do
2. L[i] = 1
3. P[i] = 0
4. forj = 1 to i-1 do
5. if S[j] < S[i] and L[j] >= L[i] then
6. L[i]= L[j]+1
7. P[i]= j
8. endif
9. endfor
10. endfor
11. Get the largest value L[k] in L[1]…L[n]
12. i = 1 // backtracking
13. j = k
14. Do
15. T[i] = S[j]
16. i++; j= P[j]
17. Until j=0
18. Output L[k] and the reverse of T.

I worte the code for this algorithm, but I am not getting how to assign values in backtracking from line 11 to 18.

clear all;
clc;
% S = input('Please enter an array> ');
S=[18 32 5 6 17 1 19 22 13];
n=length (S);
conuter = 1;
for i=1:n
L(i) = 1;
P(i) = 0;
    for j= 1:i-1 
        if S(j) < S(i) && L(j) >= L(i)
            L(i)= L(j)+1;
            P(i)= j;
        end
    end
end
L_max = max(L)
k= find(L==max(L))
i = 1;      %backtracking
j = k;
T(i) = S(j)

Answer 1

[Stephen23]

A simple recursive function does the trick:

function V = longestMono(S)
%S = [18,32,5,6,17,1,19,22,13];
V = [];
for k = 1:numel(S)
    recfun(S(k),S(k+1:end))
end
% Recursive function:
    function recfun(Z,S)
    if numel(Z)>numel(V)
        V = Z;
    end
    for k = 1:numel(S)
        if Z(end)<S(k)
            recfun([Z,S(k)],S(k+1:end))
        end
    end
    end
end

And tested:

>> S = [18,32,5,6,17,1,19,22,13];
>> V = longestMono(S)
V =
    5    6   17   19   22

Answer 2

[Guillaume]

Your question is confusing.You talk of finding "the longest monotonically increasing subsequence of a sequence of n numbers", then of "the first i letters [...] the last letter". Is it letters or numbers (not that it matters much)?

I've not tried to understand your algorithm fully but it doesn't appear to me that it's just trying to find the longest sequence. Finding the longest sequence is easily done with a single loop (explicit or implicit). It doesn't need all the backtracking that your j loop does, nor whatever that latter 'backtracking' step is:

S = [18 32 5 6 17 1 19 22 13];
ismonotonicallyincreasing = diff(S) >= 0;  %implicit loop over the elements of s
seqbounds = find(diff([false, ismonotonicallyincreasing, false]));
seqlengths = seqbounds(2:2:end) - seqbounds(1:2:end) + 1;
[maxlength, idx] = max(seqlengths);
maxsequence = S(seqbounds(idx*2-1):seqbounds(idx*2));

The same with an explicit loop, which may actually be faster:

S = [18 32 5 6 17 1 19 22 13];
maxlength = 1; maxsequence = []; curstart = 1; curlength = 1;
for idx = 2:numel(S)
    if S(idx) > S(idx-1)
        curlength = curlength + 1;
    else
        if curlength > maxlength
            maxsequence = S(curstart:idx-1);
            maxlength = curlength;
        end
        curstart = idx;
        curlength = 1;
    end
end

[Torsten]

[5 6 17 19 22] is longer than [5 6 17].

[Guillaume]

Duh! For some reason, I read the longest contiguous subsequence which is indeed not what is asked. Never mind, ignore my answer.

Leaving it there so someone else doesn't make the same mistake.

[Stephen23]

"continuous" -> contiguous ?

[Guillaume]

Stephen, probably. I'll play the non-native speaker card (although it's probably the same in French).

Answer 3

[Bilal Ghori]

I hope this would help,

clc;
clear;
%S=input('Please, Enter a sequence of numbers as a row vector:For Example:S=[s1,s2,s3,.....sn]:=')
S=[18, 32, 5, 6, 17, 1, 19, 22, 13];
disp('Input Sequence:')
disp(S)
n=length(S);

for i=1:n
    L(i)=1;
    P(i)=0;
    for j=1:i-1
        if (S(j)<S(i)) && (L(j)>=L(i))
    L(i)=L(j)+1;
    P(i)=j;
        end 
    end 
end 
i=1;    % Backtracking    
k=n-1;  %(k is the position of second last element in input sequence)
j=k;
while j>0
    T(i)=S(j);  % the resulting subsequence
    Subsequence=T(end:-1:1)
    i=i+1;
    j=P(j);
end 
  
disp('The longest monotonically increasig subsequence is:=')
disp(T(end:-1:1))

[Muhammad Usman]

I just used your code but with user input of randperm(30), it generates result that put me in confusion...please have a look

Please, Enter a sequence of numbers as a row vector:For Example:S=[s1,s2,s3,.....sn]:=randperm(30)

S =

  Columns 1 through 17

    21    14    13    18    23    27    29     8    25    22     3    11    20     2    26    15     6

  Columns 18 through 30

    12    19     5    28     1    30    10     9    16    24     4     7    17

Input Sequence:
  Columns 1 through 17

    21    14    13    18    23    27    29     8    25    22     3    11    20     2    26    15     6

  Columns 18 through 30

    12    19     5    28     1    30    10     9    16    24     4     7    17


Subsequence =

     7


Subsequence =

     6     7


Subsequence =

     3     6     7

The longest monotonically increasig subsequence is:=
     3     6     7

here is a subsequence present in these random numbers that satisfies condition i.e. 13 18 23 27 29 from position 3 to 7, but the result is very different from this.

Please give me where I am wrong

Thanks

[Stephen23]

My code gives this output:

>> longestMono(S)
ans =
   14   18   23   27   29

[Bilal Ghori]

It seems that randperm(30) generates the random permutation of integers from 1 to 30. I got this output from that code.

S =

  Columns 1 through 21

     1    13    14    28     7    24    30     4     5    29     3    15    23    18     6    27     2     9    16    22     8

  Columns 22 through 30

    25    12    17    10    11    20    26    19    21

Input Sequence:
  Columns 1 through 21

     1    13    14    28     7    24    30     4     5    29     3    15    23    18     6    27     2     9    16    22     8

  Columns 22 through 30

    25    12    17    10    11    20    26    19    21


Subsequence =

    19


Subsequence =

    17    19


Subsequence =

    16    17    19


Subsequence =

     9    16    17    19


Subsequence =

     6     9    16    17    19


Subsequence =

     5     6     9    16    17    19


Subsequence =

     4     5     6     9    16    17    19


Subsequence =

     1     4     5     6     9    16    17    19

The longest monotonically increasig subsequence is:=
     1     4     5     6     9    16    17    19

>> 

as the underlying Algorithm suggests to pick the element at second last position (k=n-1) in an input sequence and starts backtracking until ( j=0). so, it satisfies the given condition. Infact, in backtracking loop T(i)=S(j) generates subsequences that does not represent positions. Hope that, this would clear the confusion.

[Guillaume]

"It seems that randperm(30) generates the random permutation of integers from 1 to 30"

What do you mean it seems. That's exactly what randperm is defined to do. You should worry if it did anything else.

I recommend that you use format compact before generating examples to paste into answer, so that it doesn't use so much vertical space.

[Bilal Ghori]

If we start backtracking by picking an element at last position of input sequence i.e.(k=n), i got this result and the same from longstMono(S) (stephen's code),

Input Sequence:
     1     8     2     9     3    10     4     5


Subsequence =

     5


Subsequence =

     4     5


Subsequence =

     3     4     5


Subsequence =

     2     3     4     5


Subsequence =

     1     2     3     4     5

Length of longest subsequence is:=

max_length =

     5

The longest monotonically increasig subsequence is:=
     1     2     3     4     5

>> 

the same output from stephen's code longestMono(S)

longestMono

S =

     1     8     2     9     3    10     4     5


ans =

     1     2     3     4     5

this suggests that, we should start backtracking from last element of input sequence (k=n) to get the longest increasing subsequence.

[Bilal Ghori]

Guillaume, thanks for recommendation, i will definitely use format compact for next examples.

Acknowledged.