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

39 次查看（过去 30 天）
Muhammad Usman
Muhammad Usman 2018-11-16
编辑： Bilal Ghori 2018-11-17
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)

请先登录，再回答此问题。

采纳的回答

Stephen23
Stephen23 2018-11-16
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

更多回答（2 个）

Guillaume
Guillaume 2018-11-16
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
  4 个评论
显示 2更早的评论
Guillaume
Guillaume 2018-11-16
Stephen, probably. I'll play the non-native speaker card (although it's probably the same in French).

请先登录，再进行评论。

Bilal Ghori
Bilal Ghori 2018-11-16
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))
  6 个评论
显示 4更早的评论
Bilal Ghori
Bilal Ghori 2018-11-17
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
Bilal Ghori 2018-11-17
编辑：Bilal Ghori 2018-11-17
Guillaume, thanks for recommendation, i will definitely use format compact for next examples.
Acknowledged.

请先登录，再进行评论。

类别

在 Help Center 和 File Exchange 中查找有关 Signal Generation 的更多信息

标签

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by