find the longest monotonically increasing subsequence of a sequence of n numbers?
조회 수: 20 (최근 30일)
이전 댓글 표시
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
- for i=1 to n do
- L[i] = 1
- P[i] = 0
- forj = 1 to i-1 do
- if S[j] < S[i] and L[j] >= L[i] then
- L[i]= L[j]+1
- P[i]= j
- endif
- endfor
- endfor
- Get the largest value L[k] in L[1]…L[n]
- i = 1 // backtracking
- j = k
- Do
- T[i] = S[j]
- i++; j= P[j]
- Until j=0
- 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)
댓글 수: 0
채택된 답변
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
댓글 수: 0
추가 답변 (2개)
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
Guillaume
2018년 11월 16일
Stephen, probably. I'll play the non-native speaker card (although it's probably the same in French).
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
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
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에서 Whos에 대해 자세히 알아보기
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!