longest increasing subsequence
4 posters
Page 1 of 1
longest increasing subsequence
mnnit.rahul Tue Feb 03, 2009 3:06 am
find longest increasing sub-sequence in an array
mnnit.rahul- Posts : 51
Join date : 2009-02-01
Re: longest increasing subsequence
Admin Wed Feb 04, 2009 2:45 am
Admin- Admin
- Posts : 47
Join date : 2009-01-29 -
Re: longest increasing subsequence
Chunks Thu Feb 12, 2009 12:50 am
1. Make directed edges from lesser number to higher number which is coming after the shorter number.......ie
3 7 1 8
then edges from 3->7,3->8,7->8,1->8
then in this graph find the maximum length tree.
2. sort the array2,then find LCS b/w array and array2.
3 7 1 8
then edges from 3->7,3->8,7->8,1->8
then in this graph find the maximum length tree.
2. sort the array2,then find LCS b/w array and array2.
Chunks- Posts : 5
Join date : 2009-02-02
@chunks
Admin Thu Feb 12, 2009 1:58 am
yeah ur right..but there are better methods of doing it.see the wiki link(i will help u).
Admin- Admin
- Posts : 47
Join date : 2009-01-29 -
code
ramthegreatcv Mon Jun 08, 2009 7:53 pm
- Code:
#include <vector>
using namespace std;
/* Finds longest strictly increasing subsequence. O(n log k) algorithm. */
vector<int> find_lis(vector<int> &a)
{
vector<int> b, p(a.size());
int u, v;
if (a.size() < 1) return b;
b.push_back(0);
for (size_t i = 1; i < a.size(); i++) {
if (a[b.back()] < a[i]) {
p[i] = b.back();
b.push_back(i);
continue;
}
for (u = 0, v = b.size()-1; u < v;) {
int c = (u + v) / 2;
if (a[b[c]] < a[i])
u=c+1;
else
v=c;
}
if (a[i] < a[b[u]]) {
if (u > 0) p[i] = b[u-1];
b[u] = i;
}
}
for (u = b.size(), v = b.back(); u--; v = p[v]) b[u] = v;
return b;
}
/* Example of usage: */
#include <cstdio>
int main()
{
int a[] = { 1, 9, 3, 8, 11, 4, 5, 6, 4, 19, 7, 1, 7 };
vector<int> seq(a, a+sizeof(a)/sizeof(a[0]));
vector<int> lis = find_lis(seq);
for (size_t i = 0; i < lis.size(); i++)
printf("%d ",seq[lis[i]]);
printf("\n");
return 0;
}
ramthegreatcv- Posts : 55
Join date : 2009-01-30
Age : 36
Page 1 of 1
Permissions in this forum:
You cannot reply to topics in this forum|
|
|