LongestZigZagBackward

using System;
using System.Linq;

namespace LongestZigZagSequence
{
    class Program
    {
        static void Main()
        {
            var numbers = Console.ReadLine().Split().Select(s => int.Parse(s)).ToArray();
            var matrixZ = new int[numbers.Length, 2];

            for (int i = 0; i < numbers.Length; i++)
            {
                matrixZ[i, 0] = 1;
                matrixZ[i, 1] = 1;
            }
            int result = 1;
            int maxIndex = 0;

            for (int i = 1; i < numbers.Length; i++)
            {
                for (int j = 0; j < i; j++)
                {
                    if (numbers[j] < numbers[i] && matrixZ[i, 0] < matrixZ[j, 1] + 1)
                    {
                        matrixZ[i, 0] = matrixZ[j, 1] + 1;
                    }
                    if (numbers[j] > numbers[i] && matrixZ[i, 1] < matrixZ[j, 0] + 1)
                    {
                        matrixZ[i, 1] = matrixZ[j, 0] + 1;
                    }
                }
                if (result < Math.Max(matrixZ[i, 0], matrixZ[i, 1]))
                {
                    result = Math.Max(matrixZ[i, 0], matrixZ[i, 1]);
                    maxIndex = i;
                }
            }
            var finalResult = new int[result];
            var index = maxIndex;
            for (int i = numbers.Length - 1, j = result - 1; i >= 0; i--)
            {
                if (Math.Max(matrixZ[i, 0], matrixZ[i, 1]) == result)
                {
                    finalResult[j] = numbers[i];
                    j--;
                    index--;
                    result--;
                }
            }
            Console.WriteLine(string.Join(" ", finalResult));
        }
    }
}