I need to find the length of the longest strictly increasing subsequence array from a given array I just need a tip to start. Any type of help will be appreciated

15 次查看（过去 30 天）
Haseeb Hashim
Haseeb Hashim 2022-3-27
编辑： Bruno Luong 2022-3-28
How do I start to solve this problem A simple check on array for larger number than the previous one will not work in this case as we have to fin dthe longest strickly increasing subsequence..........

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

采纳的回答

Bruno Luong
Bruno Luong 2022-3-28
编辑：Bruno Luong 2022-3-28
Ran in:
Dynamic programming, it may take longtime for large array
a = [0,1,2,3,4,1,2,0,4,5,8,9,11,11,4,4,9,9];
i = longestsubseq_helper(a, -Inf)
i = 1×9
1 2 3 4 5 10 11 12 13
a(i)
ans = 1×9
0 1 2 3 4 5 8 9 11
function [i] = longestsubseq_helper(a, lo)
i = [];
maxlength = -Inf;
for j=find(a>lo)
ij = longestsubseq_helper(a(j+1:end), a(j));
if length(ij) > maxlength
maxlength = length(ij);
i = j + [0 ij];
end
end
end
  4 个评论
显示 2更早的评论
Bruno Luong
Bruno Luong 2022-3-28
编辑：Bruno Luong 2022-3-28
It matches MATLAB result, i returned is the subsequence index, you need to call
a(i)
to get the subsequence values from the original array.

请先登录，再进行评论。

更多回答（5 个）

Torsten
Torsten 2022-3-28
编辑：Torsten 2022-3-28
Here is another code that does what the OP wants (not my own work :-))
Maybe interesting for speed comparisons.
a = [0,1,2,3,4,1,2,0,4,5,8,9,11,11,4,4,9,9];
% l: length of the longest strictly monotoneous subsequence
% imon: index vector
% amon: a(imon)
[l,imon,amon] = longestsubseq(a)
function [l,imon,amon] = longestsubseq(a)
n = numel(a);
L = zeros(1,n);
P = zeros(1,n);
for i = 1:n
L(i) = 1;
P(i) = 0;
for j = 1:i-1
if a(j) < a(i) && L(j) >= L(i)
L(i) = L(j) + 1;
P(i) = j;
end
end
end
[l,k] = max(L);
i = 1;
j = k;
imon = zeros(1,l);
while j~=0
imon(i) = j;
j = P(j);
i = i+1;
end
imon = fliplr(imon);
amon = a(imon);
end
  7 个评论
显示 5更早的评论
Bruno Luong
Bruno Luong 2022-3-28
编辑：Bruno Luong 2022-3-28
I understand the code. In the next "iss" stands for incraseing subsequence, and "liss" stands for longest incraseing subsequence,
L(i) element of L array stores the length of the liss that terminates with a(i).
P(i) keeps track the previous index element (before the last a(i)) of this liss that terminates with a(i).
The first double-loop just computes L and P recursively.
The max command find the longest liss among all liss computed previously (it must terminate somwewhere right?).
Then the while loop just look back to unwrap the sequence from P.
This is O(n^2) algorithm. Not the best one according to wikipediea.

请先登录，再进行评论。

John D'Errico
John D'Errico 2022-3-27
Ran in:
  1. Can you use diff on your vector? What property does the result of diff have on strictly increasing sequences? Will all elements in such a sequence be greater than zero?
  2. Can you test to see if the elements of a vector are greater than zero?
v = rand(1,10)
v = 1×10
0.5621 0.9045 0.3177 0.7209 0.8614 0.9999 0.2485 0.7110 0.5381 0.4288
So what would this do?
result = diff(v) > 0
result = 1×9 logical array
1 0 1 1 1 0 1 0 0
Are you closer to the result you need? Yes. What property does the increasing subsequence have now? You must now find a ssequence where result is all 1. The LONGEST such subsequence corresponds to the subsequence of interest. Add 1 to that length to know the number of elements in the increasing sequence.
So now we know that the longest subsequence starts at element 3 in the original vector. The end of that subsequence is at element 6.
Now look back at my original vector v. Is that true?
If the sequence need only be non-decreasing, so you could have sequenctial elements that are identical, then just change the test to be:
result = diff(v) >= 0;
Now your problem is simpler. Find all sequences of consecutive ones. Choose the longest such sequence. I'll give you one more hint. What does this do?
startind = strfind([0,result],[0 1])
startind = 1×3
1 3 7
Can you find the end of all such subsequences in a similar way? How would you need to change that last call?
endind = strfind([result,0],[1 0]) + 1
endind = 1×3
2 6 8
  3 个评论
显示 1更早的评论
John D'Errico
John D'Errico 2022-3-27
编辑：John D'Errico 2022-3-27
The question was not specific, as to if that qualifies.
The question DID mention a comparison to the previous element, so one might presume that a subsequence must be contiguous. Until there is a statement made to the contrary, we need to make wild guesses about intention.
Haseeb Hashim
Haseeb Hashim 2022-3-28
@Torsten is right in this case does your code give 1 2 3 4 in case of 1 0 2 0 3 0 4 0 as we can skip the elements between and have 1 2 3 4 as the increasing sequence

请先登录，再进行评论。

Bruno Luong
Bruno Luong 2022-3-27
编辑：Bruno Luong 2022-3-28
Ran in:
a=rand(1,1000000);
idx=find(diff([false diff(a)>0 false]));
[lgtmax, j]=max(idx(2:2:end)-idx(1:2:end));
longestincreasedsubarray = a(idx(2*j-1)+(0:lgtmax-1))
longestincreasedseq = 1×8
0.2030 0.3815 0.4842 0.5073 0.5184 0.5463 0.5649 0.7494
  4 个评论
显示 2更早的评论

请先登录，再进行评论。

Image Analyst
Image Analyst 2022-3-27
Ran in:
If you have the Image Processing Toolbox (type ver to check if you do), then you can use regionprops():
v = [0,1,2,3,4,1,2,0,4,5,8,9,11,11,4,4,9,9]
v = 1×18
0 1 2 3 4 1 2 0 4 5 8 9 11 11 4 4 9 9
% Find out which ones are increasing.
mask = diff(v) > 0;
% Measure lengths of all runs of increasing or stable values.
props = regionprops(mask, 'Area', 'PixelList');
[maxLength, index] = max([props.Area]);
% Determine the longest length
maxLength = maxLength + 1
maxLength = 6
% Get the indexes over which the run spans:
indexes = [props(index).PixelList(:, 1); props(index).PixelList(end,1) + 1]'
indexes = 1×6
8 9 10 11 12 13
% Determine the values of the vector in that longest run:
values = v(indexes)
values = 1×6
0 4 5 8 9 11
  9 个评论
显示 7更早的评论
Haseeb Hashim
Haseeb Hashim 2022-3-28
@Torsten is right in this case as the strictly increasing subsequence is 0,1,2,3,4,5,8,9,11. I am a bsic level MATLAB user who doesnt know dynamic programming. I have searched every where but I have not found the simple solution which I can understand thanks anyways for answering my question

请先登录，再进行评论。

Image Analyst
Image Analyst 2022-3-28
Ran in:
@Haseeb Hashim, how about just a simple for loop:
% Initialize arrays
v = [0,1,2,3,4,1,2,0,4,5,8,9,11,11,4,4,9,9];
outputIndexes = -inf * ones(size(v));
outputValue = -inf *ones(size(v));
index = 1;
outputIndexes(1) = 1; % Initialize first elements.
outputValue(1) = v(1);
% Loop trying to find elements that are increasing.
for k = 2 : length(v)
if v(k) > outputValue(index)
% This element is greater than the last greatest one we had found, so record it.
index = index + 1;
outputIndexes(index) = k;
outputValue(index) = v(k);
end
end
% Crop off trailing infs.
outputIndexes = outputIndexes(1 : index)
outputIndexes = 1×9
1 2 3 4 5 10 11 12 13
outputValue = outputValue(1 : index)
outputValue = 1×9
0 1 2 3 4 5 8 9 11
  1 个评论
Torsten
Torsten 2022-3-28
编辑：Torsten 2022-3-28
Doesn't seem to work:
a = [ 0.655006 0.239884 0.873047 0.421119 0.837472 0.971189 0.600860 0.052831 ...
0.644774 0.491795 0.521089 0.587750 0.766062 0.207846 0.108566 0.924829 ...
0.249810 0.500503 0.075515 0.612612]
Output:
outputIndexes =
1 3 6
outputValue =
0.6550 0.8730 0.9712
Correct subsequence:
2 4 10 11 12 13 16
0.2399 0.4211 0.4918 0.5211 0.5878 0.7661 0.9248

请先登录，再进行评论。

类别

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

标签

产品


版本

R2017a

Community Treasure Hunt

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

Start Hunting!

Translated by