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.
