Поиск цепочки возрастания, улучшенный вариант на ссылках

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;

/// <summary>
/// Содержит информацию о ячейке двумерного Int32 массива.
/// </summary>
public class XY
{
    public XY(int x, int y, int value)
    {
        this.X = x;
        this.Y = y;
        this.Value = value;
    }

    public readonly int X, Y, Value;
    public XY next;
    public bool isEndOfThePath = false;

    public override string ToString()
    {
        return X.ToString() + ", " + Y.ToString() + ": " + Value.ToString();
    }
}

public class Program
{
    public static void Main(String[] args)
    {
        int size1 = 4000, size2 = 4000;
        arr = new int[size1,size2];

        Random random = new Random();
        for (int x = 0; x < size1; x++)
            for (int y = 0; y < size2; y++)
                arr[x, y] = random.Next();

        var timer = new Stopwatch();
        timer.Start();
        Console.WriteLine("Длина пути: {0}", GetLongestPathInArray().Count);
        timer.Stop();
        Console.WriteLine("Память: {0} MiB", Process.GetCurrentProcess().WorkingSet64 / (1024 * 1024));
        Console.WriteLine("Временя: {0} ms", timer.ElapsedMilliseconds);
    }

    public static List<XY> GetLongestPathInArray()
    {
        map = new XY[arr.GetLength(0), arr.GetLength(1)];

        for (int x = 0; x < map.GetLength(0); x++)
            for (int y = 0; y < map.GetLength(1); y++)
                map[x, y] = new XY(x, y, arr[x, y]);

        foreach (XY element in map)
            GetNext(element);

        return GetPathFrom(longestPathCell);
    }

    private static int[,] arr;
    private static XY[,] map;

    private static XY longestPathCell;
    private static int longestPathLength;

    private static XY GetNext(XY element)
    {
        //Длинно, но работает сильно быстрее, чем создание и проход по списку соседей.
        if (element.next == null && !element.isEndOfThePath)
        {
            XY left,right,down,up; //Соседи
            left = right = up = down = null;

            if (element.X > 0)
                left = map[element.X - 1, element.Y];
            if (element.X < map.GetLength(0) - 1)
                right = map[element.X + 1, element.Y];

            if (element.Y > 0)
                down = map[element.X, element.Y - 1];
            if (element.Y < map.GetLength(1) - 1)
                up = map[element.X, element.Y + 1];

            int leftLength = GetNeighbourPathLength(map, element, left);
            int rightLength = GetNeighbourPathLength(map, element, right);
            int downLength = GetNeighbourPathLength(map, element, down);
            int upLength = GetNeighbourPathLength(map, element, up);

            XY resultNeighbour = null;

            int maxLength = -1;

            if (leftLength > maxLength)
            {
                maxLength = leftLength;
                resultNeighbour = left;
            }
            if (rightLength > maxLength)
            {
                maxLength = rightLength;
                resultNeighbour = right;
            }
            if (downLength > maxLength)
            {
                maxLength = downLength;
                resultNeighbour = down;
            }
            if (upLength > maxLength)
            {
                maxLength = upLength;
                resultNeighbour = up;
            }


            element.next = resultNeighbour;

            if (resultNeighbour == null)
                element.isEndOfThePath = true;
        }

        return element.next;
    }

    private static int GetNeighbourPathLength(XY[,] map, XY parent, XY neighbour)
    {
        if (neighbour != null && neighbour.Value > parent.Value)
        {
            return GetPathLength(neighbour);
        }
        else
            return -1;
    }

    private static int GetPathLength(XY from)
    {
        int length = 0;
        XY current = from;
        while (true)
        {
            XY next = GetNext(current);

            if (next == null)
                break;
            else
            {
                length++;
                current = next;
            }
        }

        if (length > longestPathLength)
        {
            longestPathCell = from;
            longestPathLength = length;
        }

        return length;
    }

    private static List<XY> GetPathFrom(XY from)
    {
        List<XY> path = new List<XY>();
        path.Add(from);

        XY current = from;
        while (true)
        {
            XY next = GetNext(current);
            if (next == null)
                break;
            else
            {
                path.Add(next);
                current = next;
            }
        }
        return path;
    }
}