using System;

using System.Collections.Generic;

using System.Linq;

/**

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,5,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.

input: [1,4,7,2,5] => output: 4, by removing 7 from the list  [1,4,2,5]  

input: [22] => 1

input: [1,2,3,4,5,6] => output: 2

input: [1,17,7,10,13,14,8,20,5] => output: 7, by removing 13,14 from the list  [1,17,7,10,8,20,5]  

input: { 374, 40, 854, 203, 203, 156, 362, 279, 812, 955, 

600, 947, 978, 46, 100, 953, 670, 862, 568, 188, 

67, 669, 810, 704, 52, 861, 49, 640, 370, 908, 

477, 245, 413, 109, 659, 401, 483, 308, 609, 120, 

249, 22, 176, 279, 23, 22, 617, 462, 459, 244 }

Returns: 36

O(n ^ 2) Time 

*/

​

​

public class Program

{

    public static void Main()

    {

        var z = new ZigZag();

        Console.WriteLine(" Output: " + z.MaxLength(new int[]{1}));

        Console.WriteLine(" Output: " + z.MaxLength(new int[]{1, 2}));

        Console.WriteLine(" Output: " + z.MaxLength(new int[]{1, 2, 3, 4, 5, 6}));

        Console.WriteLine(" Output: " + z.MaxLength(new int[]{1, 7, 4, 9, 2, 5}));

        Console.WriteLine(" Output: " + z.MaxLength(new int[]{1,4,7,2,5}));

        Console.WriteLine(" Output: " + z.MaxLength(new int[]{1,2, 7, 4, 9, 100,80,85,82,110}));

        Console.WriteLine(" Output: " + z.MaxLength(new int[]{ 374, 40, 854, 203, 203, 156, 362, 279, 812, 955, 

                            600, 947, 978, 46, 100, 953, 670, 862, 568, 188, 

                            67, 669, 810, 704, 52, 861, 49, 640, 370, 908, 

                            477, 245, 413, 109, 659, 401, 483, 308, 609, 120, 

                            249, 22, 176, 279, 23, 22, 617, 462, 459, 244 }));

        Console.WriteLine(" Output: " + z.MaxLength2(new int[]{1}));

        Console.WriteLine(" Output: " + z.MaxLength2(new int[]{1, 2}));

        Console.WriteLine(" Output: " + z.MaxLength2(new int[]{1, 2, 3, 4, 5, 6}));

        Console.WriteLine(" Output: " + z.MaxLength2(new int[]{1, 7, 4, 9, 2, 5}));

        Console.WriteLine(" Output: " + z.MaxLength2(new int[]{1,4,7,2,5}));

        Console.WriteLine(" Output: " + z.MaxLength2(new int[]{1,2, 7, 4, 9, 100,80,85,82,110}));

        Console.WriteLine(" Output: " + z.MaxLength2(new int[]{ 374, 40, 854, 203, 203, 156, 362, 279, 812, 955, 

                            600, 947, 978, 46, 100, 953, 670, 862, 568, 188, 

                            67, 669, 810, 704, 52, 861, 49, 640, 370, 908, 

                            477, 245, 413, 109, 659, 401, 483, 308, 609, 120, 

                            249, 22, 176, 279, 23, 22, 617, 462, 459, 244 }));  

    }

}

​

public class ZigZag

{

​

    public int MaxLength2(int[] a)

    {

         Print("Input2 : ", a);

        int n = a.Length;

        if(n<=2)

            return n;

        Stack<int> up = new Stack<int>();

        Stack<int> down = new Stack<int>();

        int count = 2;

        int i = 1;

        while(i<n)

        {

            bool isPush = false;

            if(down.Count() == 0 && a[i] >= a[i-1])

            {

                up.Push(a[i++]);

                isPush = true;

            }

            else if(up.Count == 0 && a[i] <= a[i-1])

            {

                down.Push(a[i++]);

                isPush= true;

            }

            if(!isPush)

            { 

                int temp = 0;

                if(up.Count > 0)

                {

                    while(up.Count > 0)

                        temp  = up.Pop();

                    count++;

                }

                if(down.Count > 0)

                {

                    down.Clear();

                    count ++;

                }

            }

        }

        return count;

    }

    public int MaxLength(int[] a)

    {

        int maxLength = 1;

        List<int> up = new List<int>();

        List<int> down = new List<int>();

        int n = a.Length;

        Print("Input: ", a);

        up.Add(1);

        down.Add(1);

        for(int i=1; i<n; i++)

        {

            up.Add(1);

            down.Add(1);

            for(int j=0; j<i; j++)

            {

                if(a[i] > a[j])

                {

                    up[i] = Math.Max(down[j] +1 , up[i]);

                }

                else if(a[i] < a[j])

                {

                    down[i] = Math.Max(up[j]+1, down[i]);

                }

            }

            maxLength = Math.Max(maxLength, Math.Max(up[i], down[i]));

        }

        Print("Up :", up);

        Print("Down :", down);

        return maxLength;

    }

    private void Print(string s, List<int> list)

    {

        Console.Write(s + " ");

        foreach(var item in list)

        {

            Console.Write(item + " ");

        }

        Console.WriteLine(" ");

    }

    private void Print(string s, int[] a)

    {

        Print(s, a.ToList());

        //Console.Write(s + " ");

    }

    public int[] CreateTemp(int[] a)

    {

        int n = a.Length;

        int[] t = new int[n];

        for(int i=1; i<n; i++)

        {

            t[i-1] = a[i] - a[i-1];

        }

        t[n-1] = t[n-2] > 0 ? a[n-1] *-1: a[n-1];

        return t;

    }

}