Woman codesprint - minimum cost algorithm - warm up with a test case - https://codereview.stackexchange.com/questions/148523/hackerrank-woman-codesprint-minimum-cost

WomanCodeSprint_minimumCost_warmup.cs

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace minimumLoss
{
    /// <summary>
    /// 8/19/2017
    /// warmup minimum loss algorithm 
    /// 
    /// </summary>
    class Program
    {
        static void Main(string[] args)
        {           
            RunTestcase(); 
        }       

        private static void RunTestcase()
        {
            var prices = new Int64[] { 20, 7, 8, 2, 5 };

            var minimumLoss = calculateMinimumLoss(5, prices);

            // purchase at price 7, sell at price 5
            // walk through the test case, backward iterate the array, and
            // add elment one by one to the SortedSet object called sortedSet. 
            // first, sortedSet is empty, visit 5, search sortedSet a binary search tree for
            // value from [5 - minLoss + 1, 4], empty set is found. 
            // Add 5 to SortedSet object. 
            // next, visit the element 2, and then search [2 - minLoss + 1, 1], empty set is found. 
            // Add 2 to SortedSet object. 
            // third, visit the element 8, and then search [8 - minLoss + 1, 7], find {2, 5}, 
            // get max value 5, then the loss is 3. Minimum loss is udpated to 3. 
            // Add 8 to SortedSet object. 
            // fourth, visit the element 7, and then search [7 - 3 + 1, 6], in other words, [5,6], 
            // 5 is found, and then, minimum loss is updated to 2. 
            Debug.Assert(minimumLoss == 2); 
        }        
      
        /// <summary>
        /// review the function: 
        /// Time complexity analysis 
        /// Go over the array once, each visit go over the binary search tree to search a range, O(logn)
        /// So the total time complexity is O(nlogn), better than O(n^2). 
        /// </summary>
        /// <param name="n"></param>
        /// <param name="prices"></param>
        /// <returns></returns>
        private static Int64 calculateMinimumLoss(int n, Int64[] prices)
        {
            var data = new SortedSet<Int64>();

            var minLoss = Int64.MaxValue;

            // backward iteration 
            for (int i = n - 1; i >= 0; i--)
            {
                var visit = prices[i];

                // Try to find a past value less than visit, but big enough to decrease minLoss
                // (visit - minLoss, visit) is the range to search 
                var minValue = visit - minLoss + 1; 
                var maxValue = visit - 1;

                if (minValue <= maxValue)
                {
                    var sortedSet = data.GetViewBetween(minValue, maxValue);
                    if (sortedSet.Any())
                    {
                        minLoss = visit - sortedSet.Max;
                    }
                }

                data.Add(visit);
            }

            return minLoss;
        }
    }
}