Задача "Лесенка". Как улучшить? - C#
Формулировка задачи:
Здравствуйте!
У меня задание:
Коротышка шагает по целочисленному массиву. Шаг не велик, так что шагает либо на каждую ступень, либо через 1.
Нужно найти максимальную сумму элементов.
Вот мое решение, если кому-то понятней так:
Порекомендовали алгоритм сделать со сложностью O(n), а у меня он зависит от величины максимального шага, т.е. O(n2)
Может кто хотя бы на естественном языке объяснить, как ускорить до O(n)?
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]; } } }
Решение задачи: «Задача "Лесенка". Как улучшить?»
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]); }
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д