using System;

using System.Collections.Generic;

using System.Diagnostics;

​

namespace ConsoleApp3

{

    public class Program

    {

        public static void Main()

        {

            var watch = new Stopwatch();

​

            watch.Start();

​

            var prices = new[] { 1, 5, 8, 9, 10, 17, 17, 20, 23, 25, 27, 35, 41, 45, 47, 49, 50, 52, 53};

​

            var size = prices.Length;

​

            Console.WriteLine("Maximum Obtainable Value is " + RodCutting.Cut(prices, size));

​

            watch.Stop();

​

            Console.WriteLine(watch.Elapsed);

​

            Console.ReadLine();

        }

    }

​

    public class RodCutting

    {

        public static int Cut(int[] prices, int n, IDictionary<int, int> cachedResult = null)

        {

            if (cachedResult == null) cachedResult = new Dictionary<int, int>();

            var maxVal = int.MinValue;

            if (cachedResult.TryGetValue(n, out maxVal))

            {

                return maxVal;

            }

​

            if (n <= 0) return 0;

​

            for (var i = 0; i < n; i++)

            {

                maxVal = Math.Max(maxVal, prices[i] + Cut(prices, n - i - 1, cachedResult));

            }

​

            cachedResult.Add(n, maxVal);

​

            return maxVal;

        }

    }

}