How about this dp solution? Let dp[i][j][k] be the lookup table. It is defined as the longest zigzag sequence in the range i and j. k is either 0 or 1.
0- if the sequence ends with a positive difference, i.e last element is greater than the last to one. 1- if the sequence ends with a negative difference. Now we can define the recursive formula as follows, for(k=i;k<j;k++) dp[i][j][0]= max(dp[i][j][0],dp[i][k][1]+dp[k+1][j][0]) dp[i][j][1]= max(dp[i][j][1],dp[i][k][0]+dp[k+1][j][1]) correct me if i am wrong. On Fri, Jan 21, 2011 at 12:48 PM, snehal jain <[email protected]> wrote: > A sequence of numbers is called a zig-zag sequence if the differences > between successive numbers strictly alternate between positive and > negative. The first difference (if one exists) may be either positive > or negative. A sequence with fewer than two elements is trivially a > zig-zag sequence. > > For example, 1,7,4,9,2,5 is a zig-zag sequence because the differences > (6,-3,5,-7,3) are alternately positive and negative. In contrast, > 1,4,7,2,5 and 1,7,4,5,5 are not zig-zag sequences, the first because > its first two differences are positive and the second because its last > difference is zero. > > Given a sequence of integers, sequence, return the length of the > longest subsequence of sequence that is a zig-zag sequence. A > subsequence is obtained by deleting some number of elements (possibly > zero) from the original sequence, leaving the remaining elements in > their original order. > > -- > 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. > > -- S.Nishaanth, Computer Science and engineering, IIT Madras. -- 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.
