Поиск цепочки возрастания, вариант на списках

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

/// <summary>
/// Пара индексов для двумерного Int32 массива.
/// </summary>
public struct XY
{
    public XY(int x, int y)
    {
        this.x = x;
        this.y = y;
    }

    public int x, y;

    public int GetValue(int[,] arr)
    {
        return arr[x, y];
    }

    public override string ToString()
    {
        return x.ToString() + ", " + y.ToString();
    }
}

public class Program
{
    public static void Main(String[] args)
    {
        int size1 = 4000, size2 = 4000;
        int[,] 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("Длина пути: " + GetLongestPathInArray(arr).Count);
        timer.Stop();
        Console.WriteLine("Память: " + (Process.GetCurrentProcess().WorkingSet64 / (1024 * 1024)).ToString() + " MB");
        Console.WriteLine("Временя: " + timer.ElapsedMilliseconds);

        //GetLongestPathInArray(arr).ForEach(x => Console.WriteLine(x.GetValue(arr)));
    }

    /// <summary>
    /// Возвращает список элементов, обарзующих наиболее длинную цепочку возрастания в данном массиве.
    /// </summary>
    public static List<XY> GetLongestPathInArray(int[,] arr)
    {
        List<XY> longestPath = new List<XY>();
        List<XY>[,] foundWays = new List<XY>[arr.GetLength(0),arr.GetLength(1)]; //Инициализируем вспомогательный массив уже найденных цепочек

        for (int x = 0; x < arr.GetLength(0); x++)
            for (int y = 0; y < arr.GetLength(1);y++)
            {
                List<XY> path = GetLongestPathFrom(arr, new XY(x, y), foundWays);

                if (path.Count > longestPath.Count)
                    longestPath = path;
            }

        return longestPath;
    }

    /// <summary>
    /// Возвращает цепочку возрастания наибольшей длины от указанного элемента, включая его самого.
    /// </summary>
    private static List<XY> GetLongestPathFrom(int[,] arr, XY pos, List<XY>[,] foundWays)
    {
        if (foundWays[pos.x, pos.y] == null) //Если мы еще не искали цепочку для этого элемента
        {
            List<XY> neighbours = GetNeighbours(arr, pos).FindAll(n => n.GetValue(arr) > pos.GetValue(arr)); //Получаем возможные направления поиска
            List<XY> longestPath = new List<XY>();

            foreach (XY neighbour in neighbours)
            {
                List<XY> tmpPath = GetLongestPathFrom(arr, neighbour, foundWays); //Ищем наиболее "перспективного" соседа

                if (tmpPath.Count > longestPath.Count)
                    longestPath = tmpPath;
            }

            longestPath = new List<XY>(longestPath); //Необходимо клонировать, т.к. иначе будет изменяться сохраненный путь у соседа.
            longestPath.Insert(0, pos); //Добавляем себя к пути соседа и сохраняем
            foundWays[pos.x, pos.y] = longestPath;
            return longestPath;
        }
        else
            return foundWays[pos.x, pos.y];
        //Такое "кэширование" позволяет ускорить алгоритм в несколько раз, избегая повторных рассчетов одинаковых цепочек.
    }

    /// <summary>
    /// Возвращает всех соседей указанного элемента (от 2 до 4, в зависимости от индексов).
    /// </summary>
    private static List<XY> GetNeighbours(int[,] arr, XY indexes)
    {
        List<XY> result = new List<XY>(2);

        if (indexes.x > 0)
            result.Add(new XY(indexes.x - 1, indexes.y));
        if (indexes.x < arr.GetLength(0) - 1)
            result.Add(new XY(indexes.x + 1, indexes.y));

        if (indexes.y > 0)
            result.Add(new XY(indexes.x, indexes.y - 1));
        if (indexes.y < arr.GetLength(1) - 1)
            result.Add(new XY(indexes.x, indexes.y + 1));

        return result;
    }
}