@srikanth: can u frame out the recursive function for the solution proposed in DP ..... i was actually finding difficulty in this......
On Fri, Jun 8, 2012 at 5:40 PM, srikanth reddy malipatel <[email protected]> wrote: > #include<stdio.h> > > int main() > { > int Seq[100],i,j,n,Max,tmp; > int zzlen[100][2]; > scanf("%d",&n); > for(i = 0 ; i < n ; i++) { scanf("%d",&Seq[i]); zzlen[i][0] = > 1;zzlen[i][1] = 0;} > Max = 1; > for(i = 1 ; i < n ; i++) > { > for(j = i-1 ; j >= 0 ; j--) > { > if(Seq[i] >= Seq[j]) > { > tmp = 1; > if(zzlen[j][1] == -1 || zzlen[j][1] == 0) > { > if(zzlen[i][0] < zzlen[j][0]+1) { zzlen[i][0] = > zzlen[j][0]+1; zzlen[i][1] = tmp; } > } > } > if(Seq[i] < Seq[j]) > { > tmp = -1; > if(zzlen[j][1] == 1 || zzlen[j][1] == 0) > { > if(zzlen[i][0] < zzlen[j][0]+1) { zzlen[i][0] = > zzlen[j][0]+1; zzlen[i][1] = tmp;} > } > } > } > if(zzlen[i][0] > Max) Max = zzlen[i][0]; > } > printf("Length of longest zig-zag subsequence is : %d\n",Max); > return 0; > } > > On Fri, Jun 8, 2012 at 5:40 PM, srikanth reddy malipatel > <[email protected]> wrote: >> >> we should use dp >> >> >> On Fri, Jun 8, 2012 at 5:39 PM, Ratan <[email protected]> wrote: >>> >>> 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. >>> >> >> >> >> -- >> Srikanth Reddy M >> (M.Sc Tech.) Information Systems >> BITS-PILANI >> > > > > -- > Srikanth Reddy M > (M.Sc Tech.) Information Systems > BITS-PILANI > > -- > 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.
