#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.
