Given a list {x_i}, I want to find the longest increasing subsequence starting from each element such that the starting element is included in the subsequence.
The obvious way would to do this would be to perform the usual longest increasing subsequence algorithm on each element, giving O(n^2 logn). Can this be beaten?
You can use DP and bring it down to O(n^2).
Let the input be x1, x2, ..., xn
Let f1, f2, ..., fn be the length of longest increasing sequence starting from ith element. Initialize all of them to 1.
Now,
for i = n-1, n-2, .... , 1:
for j = i,i+1,...,n:
if x[i]<x[j]:
fi=max(fi, fj+1)
If you want actual sequence in addition to the length, keep track of another variable g1,g2, ..., gn where gi is the next element to follow. Initialize gis to NULL.
for i = n-1, n-2, .... , 1:
for j = i,i+1,...,n:
if x[i]<x[j]:
if fi<fj+1:
fi=fj+1
gi=j
Once you have gs, I will leave you to figure out how to enumerate the sequence starting from a particular location.
A more efficient algorithm would rely on sharing the same data structure for each iteration instead of restarting the algorithm each time. One way to do this would be to find the longest decreasing subsequence of the reverse of your input list. This should give you a data structure that gives you constant-time access to the predecessor for each element, and the length of the subsequence starting at that element.
For each starting element: if it's in the longest decreasing subsequence, follow its predecessors to the end. If it's not, find the element that is larger and to the right of it, and has the most predecessors, and follow that element's predecessors.
This would give a worst-case time complexity of O(N^2), but at least that is needed to output the results anyway.
int main(){
int arr[]={1,10,5,12,17,18,19};
int t[]={1,0,0,0,0,0,0};
int i,j;
vector<int>v[7];
v[0].push_back(1);
for(i =1;i<7;i++){
for(j =0;j<i;j++){
if(arr[j]<arr[i]){
if(t[j]>=t[i]){
t[i]=t[j]+1;
v[i].push_back(arr[j]);
}
}
}
if(i==j){
v[i].push_back(arr[i]);
}
}
for(i=0;i<7;i++){
for(j=0;j<v[i].size();j++){
cout<<v[i][j]<<" ";
}
cout<<endl;
}
return 0;
}
This is c++ code ,time complexity is N^2.I will come up with more elegant(using map with pair) solution rather than this . That will be nlogn order.I didnt write that code here because that will depends on data density .If data will be dense then i will write that approach otherwise it will always work fine.
