Thats what the question is about .... to find the maximum subsequence..... i too tried your code with the sample "10,4,12,4,1,43,21,4,1,5,7,23,9" ur code gave the result "10 12 4 43 21 23"; but the correct optimized o/p should have been with length 7 as "4,12,1,43,21,23,9"
On Fri, Jun 8, 2012 at 5:26 PM, Ashish Goel <[email protected]> wrote: > my solution will not provide the largest eg 2,4,6,5 should have largest as > 2,6,5 not 2,4.. > > Best Regards > Ashish Goel > "Think positive and find fuel in failure" > +919985813081 > +919966006652 > > > On Fri, Jun 8, 2012 at 4:15 PM, Ashish Goel <[email protected]> wrote: >> >> O(n) is straight forward >> >> bool increase = true; >> int j = 0; >> result[j++]=a[0]; >> for (int i=1;i<n;i++) >> { >> if ((increase) >> { >> if (result[j-1]<a[i])) >> { >> result[j++] = a[i]; >> increase = false; >> } >> } >> else { >> if (result[j-1] >a[i])) >> { >> result[j++] = a[i]; >> increase = true; >> } >> } >> } >> >> What i was thinking is to find the number of peaks and valleys through >> binary search thereby using log(n) solution not able to conceptualize it >> this way (:. >> Best Regards >> Ashish Goel >> "Think positive and find fuel in failure" >> +919985813081 >> +919966006652 >> >> >> >> On Fri, Jun 8, 2012 at 3:47 PM, Ratan <[email protected]> wrote: >>> >>> Given a list of integers n, we have to find the length of largest >>> zigazg subsequence in the list.... i.e,zigzag subsequence is defined >>> as "if the first number is increasing then the 2nd one should be >>> decreasing or vice versa...... " >>> >>> for eg : if list[n]={1,10,5,9,8,12,20} then, >>> >>> largest zigzag subsequence will be : {1,10,5,9,8,12} or >>> {1,10,5,9,8,20} and length will be=6; >>> >>> >>> -- >>> -- >>> >>> -- >>> 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. >>> >> > > -- > 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. -- -- Ratan | 3rd Year | Information Technology | NIT ALLAHABAD -- 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.
