Re: [algogeeks] Longest Increasing Subsequence in O(nlogn)
http://codepad.org/EWcoJ2c3 Here is solution for find the Longest Increasing subseqence. I tried two approach. 1. Find the suboptimal solution using O(n) complexity thereby optimal solution for the problem reaches O(n^2). 2. Find the suboptimal solution using O(logn) complexity thereby optimal solution for the problem reaches O(nlogn). On Fri, Jun 4, 2010 at 11:49 PM, Anand anandut2...@gmail.com wrote: http://codepad.org/NDAeIpxR Here is code for it On Sat, May 29, 2010 at 7:45 PM, Anurag Sharma anuragvic...@gmail.comwrote: @pawan Will it not take O(n^2) time then. What he is talking about is solving it in O(nlogn) time Anurag Sharma http://anuragsharma-sun.blogspot.com/ On Sat, May 29, 2010 at 7:04 PM, pawan sharma pawanprakash...@gmail.comwrote: @amit for longest increasing subsequence , just sort the given array and find longest subsequence of sorted array and unsorted array . It will give you longest increasing subsequence (because of sorted array) . On Sat, May 29, 2010 at 12:41 PM, Nikhil Agarwal nikhil.bhoja...@gmail.com wrote: Check: http://www.algorithmist.com/index.php/Longest_Increasing_Subsequence On Sat, May 29, 2010 at 4:15 AM, Amir hossein Shahriari amir.hossein.shahri...@gmail.com 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 amitjaspal...@gmail.com 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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . 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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . 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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . 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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . 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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . 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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Longest Increasing Subsequence in O(nlogn)
http://codepad.org/NDAeIpxR Here is code for it On Sat, May 29, 2010 at 7:45 PM, Anurag Sharma anuragvic...@gmail.comwrote: @pawan Will it not take O(n^2) time then. What he is talking about is solving it in O(nlogn) time Anurag Sharma http://anuragsharma-sun.blogspot.com/ On Sat, May 29, 2010 at 7:04 PM, pawan sharma pawanprakash...@gmail.comwrote: @amit for longest increasing subsequence , just sort the given array and find longest subsequence of sorted array and unsorted array . It will give you longest increasing subsequence (because of sorted array) . On Sat, May 29, 2010 at 12:41 PM, Nikhil Agarwal nikhil.bhoja...@gmail.com wrote: Check: http://www.algorithmist.com/index.php/Longest_Increasing_Subsequence On Sat, May 29, 2010 at 4:15 AM, Amir hossein Shahriari amir.hossein.shahri...@gmail.com 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 amitjaspal...@gmail.com 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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . 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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . 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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . 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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . 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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . 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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Longest Increasing Subsequence in O(nlogn)
Check:
http://www.algorithmist.com/index.php/Longest_Increasing_Subsequence
On Sat, May 29, 2010 at 4:15 AM, Amir hossein Shahriari
amir.hossein.shahri...@gmail.com 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 amitjaspal...@gmail.com 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 algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
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 algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
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 algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
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(vectorint a, vectorint b)
{
vectorint 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 };
vectorint seq(a, a+sizeof(a)/sizeof(a[0]));
vectorint lis;
find_lis(seq, lis);
for (size_t i = 0; i lis.size(); i++)
printf(%d , seq[lis[i]]);
printf(\n);
return 0;
}
Re: [algogeeks] Longest Increasing Subsequence in O(nlogn)
Hi Amit, Could you just elaborate which algorithm are you talking about. Is it KMP algorithm for string matching are looking at. Thanks, Anand On Fri, May 28, 2010 at 8:14 AM, amit amitjaspal...@gmail.com 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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . 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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
