Check:
http://www.algorithmist.com/index.php/Longest_Increasing_Subsequence
On Sat, May 29, 2010 at 4:15 AM, Amir hossein Shahriari <
[email protected]> wrote:
> A hint from "Introduction to algorithms" on this problem:
> Observe that the last element of a candidate subsequence of length *i* is
> at least as large as the last element of a candidate subsequence of length
> *i-1. *Maintain candidate subsequences by linking them through the input
> sequence
>
> The attached file is a tutorial from train.usaco.org which includes 3
> approaches to the problem and explains them with some examples.
> I hope it would help!
>
>
> On Fri, May 28, 2010 at 7:44 PM, amit <[email protected]> wrote:
>
>> Hi , Can anyone plz explain this algorithm taking some example.
>> I read this on wiki but could'nt get how binary search was working.
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to [email protected].
>> To unsubscribe from this group, send email to
>> [email protected]<algogeeks%[email protected]>
>> .
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to [email protected].
> To unsubscribe from this group, send email to
> [email protected]<algogeeks%[email protected]>
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
--
Thanks & Regards
Nikhil Agarwal
Senior Undergraduate
Computer Science & Engineering,
National Institute Of Technology, Durgapur,India
http://tech-nikk.blogspot.com
http://beta.freshersworld.com/communities/nitd
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
#include <vector>
using namespace std;
/* Finds longest strictly increasing subsequence. O(n log k) algorithm. */
void find_lis(vector<int> &a, vector<int> &b)
{
vector<int> p(a.size());
int u, v;
if (a.empty()) return;
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;
}
/* Example of usage: */
#include <cstdio>
int main()
{
int a[] = { 9,10,11,12,1,2,3,4,5,6,7 };
vector<int> seq(a, a+sizeof(a)/sizeof(a[0]));
vector<int> lis;
find_lis(seq, lis);
for (size_t i = 0; i < lis.size(); i++)
printf("%d ", seq[lis[i]]);
printf("\n");
return 0;
}
