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

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 List<XY> GetNeighbours(XY[,] map)
    {
        List<XY> result = new List<XY>(2);

        if (X > 0)
            result.Add(map[X - 1, Y]);
        if (X < map.GetLength(0) - 1)
            result.Add(map[X + 1, Y]);

        if (Y > 0)
            result.Add(map[X, Y - 1]);
        if (Y < map.GetLength(1) - 1)
            result.Add(map[X, Y + 1]);

        return result;
    }
    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;
        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)));
    }

    public static List<XY> GetLongestPathInArray(int[,] arr)
    {
        XY[,] 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]);

        int length = -1;
        XY bestElement = null;
        foreach (XY element in map)
        {
            int tmpLength = GetPathLength(map, map[element.X, element.Y]);
            if (tmpLength > length)
            {
                bestElement = element;
                length = tmpLength;
            }
        }

        return GetPathFrom(map, bestElement);
    }

    private static XY GetNext(XY[,] map, XY element)
    {
        if (element.next == null && !element.isEndOfThePath)
        {
            List<XY> neighbours = element.GetNeighbours(map).FindAll(n => n.Value > element.Value);

            if (neighbours.Count == 0)
                element.isEndOfThePath = true;
            else
            {
                int maxLength = -1;
                XY resultNeighbour = null;
                foreach (XY neighbour in neighbours)
                {
                    int length = GetPathLength(map, neighbour);
                    if (length > maxLength)
                    {
                        resultNeighbour = neighbour;
                        maxLength = length;
                    }
                }

                element.next = resultNeighbour;
            }
        }

        return element.next;
    }

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

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

        return length;
    }

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

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

        return path;
    }
}