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

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..........

Answer 1

[Bruno Luong]

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

[Haseeb Hashim]

Thankyou for responding. I have a question

What is "lo" for as input to function Can we define it inside the function itself So that only input is the array we need the subsequence for ?

[Bruno Luong]

Just define a wrapper

function i = longestsubseq(a)
i = longestsubseq_helper(reshape(a, 1, []), -Inf)
end

then call

i = longestsubseq(a)

lo is used to check recursively the sequence is strictly increasing with the statement

find(a> lo)

[Torsten]

I did not yet try to exactly understand the code, but under octave, I get

i =

1    2    3    4    5   10   11   12   13

Strange, isn't it ?

[Bruno Luong]

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.

Answer 2

[Torsten]

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

[Bruno Luong]

"not my own work :-)"

who is, please?

[Torsten]

https://de.mathworks.com/matlabcentral/answers/430207-find-the-longest-monotonically-increasing-subsequence-of-a-sequence-of-n-numbers

I don't know the book from which the algorithm is taken.

Seems to be a well-known problem, solvable in O(n*log(n)):

https://en.wikipedia.org/wiki/Longest_increasing_subsequence

[Bruno Luong]

For sure I'll look at other people's work.

[Haseeb Hashim]

wonderful @Torsten thanks again, This code works perfectly I hope someday I will be able to make such difficult functions , thanks again

[Image Analyst]

@Torsten, glad to hear it. I would expect that you wouldn't write code like that -- an uncommented, alphabet soup of variable names that's very difficult to understand. I'm sure you would have used more descriptive variable names, and plentiful comments, to make the code easier to follow.

[Torsten]

@Image Analyst

I would have inserted comments if I had understood the code :-)

[Bruno Luong]

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.

Answer 3

[John D'Errico]

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

[Torsten]

What about the sequence

1 0 2 0 3 0 4 0 ...

Subsequence is

1 2 3 4 ...

?

[John D'Errico]

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]

@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

Answer 4

[Bruno Luong]

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

[Torsten]

a = [0 1 0 2 0 3 0 4 0 5 0 6 0 7 0 8 0 9 0 10];

?

The longest strictly increasing subsequence array is

[1 2 3 4 5 6 7 8 9 10]

[Bruno Luong]

If that is the request, I guess the problem is NP-hard.

[Haseeb Hashim]

what do you mean by NP-hard and this code isnt giving me the right answer

[Bruno Luong]

NP-hard https://en.wikipedia.org/wiki/NP-hardness

The above code give longest subarray and not subsequence.

Answer 5

[Image Analyst]

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

[Torsten]

... but the longest subsequence array is 0,1,2,3,4,5,8,9,11.

[Image Analyst]

@Torsten, no because after 0,1,2,3,4 it dips down to zero. It's no longer strictly increasing once it goes from 4 down to 0 -- it's decreasing at that point.

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

plot(v, 'b.-', 'LineWidth', 2, 'MarkerSize', 40);
grid on;

[Bruno Luong]

No ImageAnalyst, you miss the point: Torsen raises the question of definition of "subsequence" he is right, mathematcally subsequence must not be contiguous according to some definition I read somewhere else, so where as the values of array drop in between selected subset of increasing indices it doesn't matter. "subarray" is the terme used for contiguous subsequence. OP uses the "subsequence array", which has not universal definiiion.

[Image Analyst]

Well I agree with John so I guess we'll just have to disagree unless/until the original poster clarifies, like if he requires that the "subsequence must not be contiguous". But, unlike you, I've never heard of strictly increasing sequences having elements inside that are less than the immediately prior element.

[Bruno Luong]

Here we go the definition of subsequence

https://en.wikipedia.org/wiki/Subsequence

https://mathworld.wolfram.com/Subsequence.html

https://www.geeksforgeeks.org/subarraysubstring-vs-subsequence-and-programs-to-generate-them/

So based on this definition Torsen subsequence is strictly increaseing and longest. You cannot tell Torsen statement is wrong until we know the definition of "subsequence".

[Torsten]

@Image Analyst

But, unlike you, I've never heard of strictly increasing sequences having elements inside that are less than the immediately prior element.

The strict monotonicity is about the subsequence, not the sequence itself.

For subsequences being strictly increasing, the original sequence does not need to have this property.

[Image Analyst]

OK by that definition you may be right. Hopefully we'll hear from the original poster which way he wants it. And, the context from which this need arises, which may give us some insight, since we all know that what the poster asks for is not always what they need.

[Torsten]

Yes, I also tend to your interpretation because the other task would be too hard for an assignment :-)

[Haseeb Hashim]

@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

Answer 6

[Image Analyst]

@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

[Torsten]

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