if all the elements are positive then we can reverse the array and multiply all of them by -1. Now apply LIS algorithm O(nlog(n)) and since it gives the answer for all k<=n with the minimum sum, this will be the answer multiplied by -1.
On Sat, Oct 26, 2013 at 12:12 AM, kumar raja <rajkumar.cs...@gmail.com>wrote: > I think O(nlogn) solution is possible for this problem. First find the > largest increasing subsequence in O(nlogn) time. > > http://en.wikipedia.org/wiki/Longest_increasing_subsequence#Efficient_algorithms > > From this one u have LIS array M and parent array P. Now traverse through > the array M and for all the length values >= k , u can print the "k" > elements using Parent array P. I guess the step of printing the array > elements wont be greater than O(n logn). > > So it is bounded by O(nlogn) . In the worst case it might go up to > O(n^2). But i am not sure of this. > > > On 25 October 2013 00:17, atul anand <atul.87fri...@gmail.com> wrote: > >> OK, i got now why you were using min-heap. >> >> now consider this example :- >> >> 200,12,33,1,55,100 >> >> K=3 >> >> insert 200 >> 12 < 200...cannot insert >> 33 < 200...cannot insert >> . >> . >> . >> 100<200 cannot insert >> >> output : 200 (not lenght of k) >> output should be : 33,55,100 >> >> >> On 10/24/13, pankaj joshi <joshi10...@gmail.com> wrote: >> > Max-heap should not used in this case, >> > why min heap? -- this is because program has to decide the smallest >> element >> > in k-group. >> > in your example if i consider k =3 than >> > >> > insert 1 >> > insert 2 >> > insert 5 >> > insert 10 >> > size of heap ==4 so delete root of min- heap (which is 1), >> > insert 100 >> > 30 cant insert because temp = 100 and 30<temp >> > insert 8 cant insert temp = 100 and 8<temp >> > (500>temp)size of heap ==4 so delete root of min-heap(which is 2) >> > insert 555 >> > >> > now if i check the heap elements >> > {5, 10, 100 , 555} >> > >> > >> > >> > On Thu, Oct 24, 2013 at 11:25 PM, atul anand >> > <atul.87fri...@gmail.com>wrote: >> > >> >> in your updated algo , you should be using max-heap not min-heap. >> >> >> >> check your algo for :- >> >> >> >> 1,2,5,10,100,30,8,555 >> >> >> >> let me know if it work fine.If it is working fine then i need more >> >> clarity of your algo >> >> >> >> On 10/24/13, pankaj joshi <joshi10...@gmail.com> wrote: >> >> > @Saurabh: >> >> > As per the question the elements of sub-sequence should be >> increasing, >> >> > so the solution will be {5} and as per the program. >> >> > * but as written longest sub-sequence of k =2, so it should be {2,3} >> >> > for >> >> > this case. (there should be backtrack in this case.) >> >> > >> >> > @atul: increasing sub sequence is checked by condition, not by >> >> > Min-heap, >> >> > but min heap is used for storing the largest elements. >> >> > So it is preferable DS, >> >> > >> >> > >> >> > On Thu, Oct 24, 2013 at 8:35 PM, atul anand <atul.87fri...@gmail.com >> > >> >> > wrote: >> >> > >> >> >> @pankaj : how can you maintain increasing sub-sequence using >> >> >> heap....your soln is for finding finding K largest element in the >> >> >> array...so it wont work. >> >> >> >> >> >> On 10/24/13, Saurabh Paliwal <saurabh.paliwa...@gmail.com> wrote: >> >> >> > check for {5,2,3} and K = 2. >> >> >> > >> >> >> > >> >> >> > >> >> >> > On Thu, Oct 24, 2013 at 7:41 PM, pankaj joshi < >> joshi10...@gmail.com> >> >> >> wrote: >> >> >> > >> >> >> >> @ Saurabh, >> >> >> >> >> >> >> >> I have done a correction on algo >> >> >> >> >> >> >> >> temp =0 >> >> >> >> loop n to a[] >> >> >> >> if a[i]>temp >> >> >> >> if min-heap(root) < a[i] >> >> >> >> if min-heap(count)==k >> >> >> >> delete root in min- heap >> >> >> >> inseart a[i] in min - heap >> >> >> >> >> >> >> >> As i have made the condition: min-heap, (condition size should be >> >> >> >> always >> >> >> >> k) for this particular case. >> >> >> >> >> >> >> >> And in the example {5,2,1,10,9,30,8,55} if K =3 >> >> >> >> >> >> >> >> insert 5 >> >> >> >> 2 is less so do nothing >> >> >> >> 1 is less so do nothing >> >> >> >> insert 10 >> >> >> >> 9 is less so do nothing >> >> >> >> insert 30 >> >> >> >> 8 is less so do nothing >> >> >> >> insert 55 (before inserting 50 delete the root of heap as count >> of >> >> >> >> heap >> >> >> >> == >> >> >> >> 3), deleted root was - 5 >> >> >> >> so the output will be >> >> >> >> {10,30,55} >> >> >> >> >> >> >> >> and if k is 4 >> >> >> >> than >> >> >> >> {5, 10, 30 , 55) >> >> >> >> >> >> >> >> >> >> >> >> On Thu, Oct 24, 2013 at 6:20 PM, Saurabh Paliwal < >> >> >> >> saurabh.paliwa...@gmail.com> wrote: >> >> >> >> >> >> >> >>> You must be mistaken in the definition of heaps, or maybe the >> >> >> >>> question, >> >> >> >>> look at the updated question I put up there. >> >> >> >>> >> >> >> >>> >> >> >> >>> On Thu, Oct 24, 2013 at 5:48 PM, pankaj joshi >> >> >> >>> <joshi10...@gmail.com>wrote: >> >> >> >>> >> >> >> >>>> >> >> >> >>>> hi all, >> >> >> >>>> >> >> >> >>>> nlog(k) is the solution i think. >> >> >> >>>> can anyone suggest more optimal? >> >> >> >>>> solution: >> >> >> >>>> create a min-heap, (condition size should be always k) >> >> >> >>>> >> >> >> >>>> temp =0 >> >> >> >>>> loop n to a[] >> >> >> >>>> if a[i]>temp >> >> >> >>>> if min-heap(root) < a[i] >> >> >> >>>> delete root in min- heap >> >> >> >>>> inseart a[i] in min - heap >> >> >> >>>> >> >> >> >>>> at the end of main loop the min-heap will contain the final >> >> >> >>>> sequence. >> >> >> >>>> >> >> >> >>>> On Thu, Oct 24, 2013 at 8:50 AM, atul anand >> >> >> >>>> <atul.87fri...@gmail.com>wrote: >> >> >> >>>> >> >> >> >>>>> @Saurabh Paliwal : yes >> >> >> >>>>> >> >> >> >>>>> On 10/24/13, Saurabh Paliwal <saurabh.paliwa...@gmail.com> >> >> >> >>>>> wrote: >> >> >> >>>>> > Do you mean >> >> >> >>>>> > *of all the increasing subsequences of length k in this >> array, >> >> >> >>>>> > find >> >> >> >>>>> the one >> >> >> >>>>> > with maximum sum ?* >> >> >> >>>>> > >> >> >> >>>>> > >> >> >> >>>>> > >> >> >> >>>>> > On Wed, Oct 23, 2013 at 10:52 PM, atul anand >> >> >> >>>>> > <atul.87fri...@gmail.com>wrote: >> >> >> >>>>> > >> >> >> >>>>> >> Given an array with N elements and integer K . Find sum of >> >> >> >>>>> >> longest >> >> >> >>>>> >> increasing sub-sequence of length K elements such that >> >> >> >>>>> >> sub-sequence >> >> >> >>>>> >> found >> >> >> >>>>> >> is maximum among all K max su-sequence. >> >> >> >>>>> >> >> >> >> >>>>> >> Eg arr[]={5,2,1,10,9,30,8,55} >> >> >> >>>>> >> >> >> >> >>>>> >> K = 3 >> >> >> >>>>> >> output : 10,30,55 sum = 10+30+55 = 95 >> >> >> >>>>> >> >> >> >> >>>>> >> if K=4 >> >> >> >>>>> >> output : 5,10,30,55 sum = 5+10+30+55 =100 >> >> >> >>>>> >> >> >> >> >>>>> >> -- >> >> >> >>>>> >> You received this message because you are subscribed to the >> >> >> >>>>> >> Google >> >> >> >>>>> Groups >> >> >> >>>>> >> "Algorithm Geeks" group. >> >> >> >>>>> >> To unsubscribe from this group and stop receiving emails >> from >> >> >> >>>>> >> it, >> >> >> >>>>> send an >> >> >> >>>>> >> email to algogeeks+unsubscr...@googlegroups.com. >> >> >> >>>>> >> >> >> >> >>>>> > >> >> >> >>>>> > >> >> >> >>>>> > >> >> >> >>>>> > -- >> >> >> >>>>> > - Saurabh Paliwal >> >> >> >>>>> > >> >> >> >>>>> > B-Tech. Comp. Science and Engg. >> >> >> >>>>> > >> >> >> >>>>> > IIT ROORKEE >> >> >> >>>>> > >> >> >> >>>>> > -- >> >> >> >>>>> > You received this message because you are subscribed to the >> >> >> >>>>> > Google >> >> >> >>>>> Groups >> >> >> >>>>> > "Algorithm Geeks" group. >> >> >> >>>>> > To unsubscribe from this group and stop receiving emails >> from >> >> it, >> >> >> >>>>> send an >> >> >> >>>>> > email to algogeeks+unsubscr...@googlegroups.com. >> >> >> >>>>> > >> >> >> >>>>> >> >> >> >>>>> -- >> >> >> >>>>> You received this message because you are subscribed to the >> >> >> >>>>> Google >> >> >> >>>>> Groups "Algorithm Geeks" group. >> >> >> >>>>> To unsubscribe from this group and stop receiving emails from >> >> >> >>>>> it, >> >> >> send >> >> >> >>>>> an email to algogeeks+unsubscr...@googlegroups.com. >> >> >> >>>>> >> >> >> >>>> >> >> >> >>>> >> >> >> >>>> >> >> >> >>>> -- >> >> >> >>>> Regards, >> >> >> >>>> >> >> >> >>>> Pankaj Kumar Joshi >> >> >> >>>> >> >> >> >>>> -- >> >> >> >>>> You received this message because you are subscribed to the >> >> >> >>>> Google >> >> >> >>>> Groups "Algorithm Geeks" group. >> >> >> >>>> To unsubscribe from this group and stop receiving emails from >> it, >> >> >> >>>> send >> >> >> >>>> an email to algogeeks+unsubscr...@googlegroups.com. >> >> >> >>>> >> >> >> >>> >> >> >> >>> >> >> >> >>> >> >> >> >>> -- >> >> >> >>> - Saurabh Paliwal >> >> >> >>> >> >> >> >>> B-Tech. Comp. Science and Engg. >> >> >> >>> >> >> >> >>> IIT ROORKEE >> >> >> >>> >> >> >> >>> -- >> >> >> >>> You received this message because you are subscribed to the >> Google >> >> >> >>> Groups >> >> >> >>> "Algorithm Geeks" group. >> >> >> >>> To unsubscribe from this group and stop receiving emails from >> it, >> >> >> >>> send >> >> >> >>> an >> >> >> >>> email to algogeeks+unsubscr...@googlegroups.com. >> >> >> >>> >> >> >> >> >> >> >> >> >> >> >> >> >> >> >> >> -- >> >> >> >> Regards, >> >> >> >> >> >> >> >> Pankaj Kumar Joshi >> >> >> >> >> >> >> >> -- >> >> >> >> You received this message because you are subscribed to the >> Google >> >> >> Groups >> >> >> >> "Algorithm Geeks" group. >> >> >> >> To unsubscribe from this group and stop receiving emails from it, >> >> send >> >> >> an >> >> >> >> email to algogeeks+unsubscr...@googlegroups.com. >> >> >> >> >> >> >> > >> >> >> > >> >> >> > >> >> >> > -- >> >> >> > - Saurabh Paliwal >> >> >> > >> >> >> > B-Tech. Comp. Science and Engg. >> >> >> > >> >> >> > IIT ROORKEE >> >> >> > >> >> >> > -- >> >> >> > You received this message because you are subscribed to the Google >> >> >> > Groups >> >> >> > "Algorithm Geeks" group. >> >> >> > To unsubscribe from this group and stop receiving emails from it, >> >> >> > send >> >> >> > an >> >> >> > email to algogeeks+unsubscr...@googlegroups.com. >> >> >> > >> >> >> >> >> >> -- >> >> >> You received this message because you are subscribed to the Google >> >> Groups >> >> >> "Algorithm Geeks" group. >> >> >> To unsubscribe from this group and stop receiving emails from it, >> send >> >> an >> >> >> email to algogeeks+unsubscr...@googlegroups.com. >> >> >> >> >> > >> >> > >> >> > >> >> > -- >> >> > Regards, >> >> > >> >> > Pankaj Kumar Joshi >> >> > >> >> > -- >> >> > You received this message because you are subscribed to the Google >> >> > Groups >> >> > "Algorithm Geeks" group. >> >> > To unsubscribe from this group and stop receiving emails from it, >> send >> >> > an >> >> > email to algogeeks+unsubscr...@googlegroups.com. >> >> > >> >> >> >> -- >> >> You received this message because you are subscribed to the Google >> Groups >> >> "Algorithm Geeks" group. >> >> To unsubscribe from this group and stop receiving emails from it, send >> an >> >> email to algogeeks+unsubscr...@googlegroups.com. >> >> >> > >> > >> > >> > -- >> > Regards, >> > >> > Pankaj Kumar Joshi >> > >> > -- >> > You received this message because you are subscribed to the Google >> Groups >> > "Algorithm Geeks" group. >> > To unsubscribe from this group and stop receiving emails from it, send >> an >> > email to algogeeks+unsubscr...@googlegroups.com. >> > >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To unsubscribe from this group and stop receiving emails from it, send an >> email to algogeeks+unsubscr...@googlegroups.com. >> > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to algogeeks+unsubscr...@googlegroups.com. > -- - Saurabh Paliwal B-Tech. Comp. Science and Engg. IIT ROORKEE -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com.
