Hi there,
I'm developing a program that for a part of it I need to find all maximal increasing subsequences of a sequence of integer.
I try to clarify the problem :
Given sequence of Integer S={1,5,6,9,2,3,4,7,8}
I want to find all maximal increasing subsequence of S.
a maximal increasing subsequence is a subsequence that its items are ordered increasingly and it's not a subsequence of other subsequences (maximal). It can have any size.
for example : S1={1,5,6,9} or S2={1,5,6,7,8} are maximal increasing subsequence of S as the items are increasing and one can not find any other subsequence who is super sequence of them. BUT S3={1,5,6,2} is not increasing or S4={6,7,8} is not maximal as there is a subsequence like S5={1,5,6,7,8}.
There is alot of works to find "LIS" (longest increasing subsequence) even some that work with O(n log n) complexity but they give just longest increasing sequence but not all increasing subsequences from any size.
I have an algo to do that but it's O(nē) but I like to find one with higher performance.
I should notice that it's possible to have few increasing subsequences who have the same size but are different.
I will be so thankful if you give an algo complete it with a pesudo code to better inspire the used data structure.
Many thanks.
