@topcoder: If i understood it correctly, what you are trying to do here, is basically check whether A[i] > A[j], then take the length of the max sequence that is zigzag ending at A[j] with the last difference being negative i.e. A[j] - A[previous index in zig-zag seq] is negative, otherwise vice versa.
On Dec 16, 11:55 am, top coder <[email protected]> wrote: > int LIDS ( vector<int> a , int n ){ > int s[51][2]; > for(int i = 0 ; i < n ; i++) > for(int j = 0 ; j < 2 ; j++) > s[i][j] = 1; > > for(int i = 0 ; i < n ; i++){ > for(int j = 0 ; j < i ; j++){ > if( a[i] != a[j] ){ > s[i][a[i]>a[j]] = max(s[j][a[i]<a[j]] + 1 , s[i] > [a[i]>a[j]]); > } > } > } > > return max( s[n-1][0] , s[n-1][1] ); > > } > > On Dec 16, 10:09 am, Azhar Hussain <[email protected]> wrote: > > > > > > > > > It is dynamic programming. > > Search in topcoder algo tutorials > > > On Dec 16, 2011 10:33 AM, "Sangeeta" <[email protected]> wrote: > > > > Problem Statement > > > 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].> For more options, visit this group > > at > > >http://groups.google.com/group/algogeeks?hl=en. > > > - Hide quoted text - > > > - Show quoted text -- Hide quoted text - > > > - Show quoted text - -- 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.
