Задача "Лесенка". Как улучшить? - C#

Формулировка задачи:

Здравствуйте! У меня задание: Коротышка шагает по целочисленному массиву. Шаг не велик, так что шагает либо на каждую ступень, либо через 1. Нужно найти максимальную сумму элементов. Вот мое решение, если кому-то понятней так:

                    Листинг программы
                
 
                            
                        
    class Program
    {
        static void Main(string[] args)
        {
            int[] arr = new int[] {0, -3, -5, -12, -125, -21, -122, -150, 150, -155, 0};
            int[] way = new int[arr.Length];
            
            Console.WriteLine(Sum(arr,0,way));
            /* Проверка
            int i = 0;
            while (i<way.Length-1)
            {
                Console.Write(way[i] + "->");
                i += way[i];
            }
            Console.WriteLine("Done");*/
            Console.ReadKey();
        }
        
        static float Sum(int[]arr, int position, int[] way)
        {
            if(position>=arr.Length)
            {
                return 0;
            }
            float a = Sum(arr, position + 1,way);
            float b = Sum(arr, position + 2,way);
            if (a > b)
            {
                way[position] = 1;
                return a+arr[position];
            }
            else
            {
                way[position] = 2;
                return b+arr[position];
            }
        }
    }

Порекомендовали алгоритм сделать со сложностью O(n), а у меня он зависит от величины максимального шага, т.е. O(n²) Может кто хотя бы на естественном языке объяснить, как ускорить до O(n)?

Решение задачи: «Задача "Лесенка". Как улучшить?»

textual
                            Листинг программы 
                        
 
                        
                          
                    
    static long MySum(int[] arr)
    {
        if (arr.Length == 0)
            return 0;
            
        if (arr.Length == 1)
            return Math.Max(0, arr[0]);
            
        var sums = new long[arr.Length];
        
        sums[sums.Length - 1] = arr.Last();
        sums[sums.Length - 2] = arr[sums.Length - 2] + Math.Max(arr.Last(), 0);
        
        for (int i = sums.Length - 3; i >= 0; i--)
        {
            sums[i] = Math.Max(sums[i + 1], sums[i + 2]) + arr[i];
        }
        
        return Math.Max(sums[0], sums[1]);
    }