/*
     * minimum loss       
     * 
     * read Java TreeSet floor method:
     * https://www.tutorialspoint.com/java/util/treeset_floor.htm
     * 
     * use C# List<T> BinarySearch, Insert API
     * https://msdn.microsoft.com/en-us/library/w4e7fxsh(v=vs.110).aspx
     *      
     * 
     * The idea is to go over each house in the reverse order, add one by one into the List object, but
     * the List is also a binary search tree. How to do it? To maintain the binary search tree, 
      * using BinarySearch to find the position first, similar to Java TreeSet class floor method, 
     * meanwhile, update minimum loss value if the insertion position is not the smallest one in the tree. 
     * 
     * Go over each house once, each time, binary search will take O(logn) time. Therefore, the final 
     * time complexity should be O(nlogn). 
     */
    private static Int64 MinimumLossCal(int n, Int64[] prices)
    {
        List<Int64> data = new List<Int64>();

        Int64 minLoss = Int64.MaxValue;

        for (int i = n - 1; i >= 0; i--)
        {
            Int64 curPrice = prices[i];
            var index = data.BinarySearch(curPrice);
            if (index < 0)
            {
                int pos = ~index;
                if (pos > 0)
                {
                    Int64 newDiff = curPrice - data[pos - 1];

                    minLoss = (newDiff < minLoss) ? newDiff : minLoss;
                }

                data.Insert(pos, curPrice);
            }

            // if there is one in the binary search tree, then no need to insert the duplicate one in the tree.                
        }

        return minLoss;
    }

 /*
     * minimum loss       
     * 
     * read Java TreeSet floor method:
     * https://www.tutorialspoint.com/java/util/treeset_floor.htm
     * 
     * use C# List<T> BinarySearch, Insert API
     * https://msdn.microsoft.com/en-us/library/w4e7fxsh(v=vs.110).aspx
     *      
     * 
     * The idea is to go over each house in the reverse order, add one by 
     * one into the List object, but
     * the List cannot be a binary search tree.  
     * Using BinarySearch to find the position first (Time complexity  
     * O(n)), similar to Java TreeSet class floor method, but Insert 
     * takes O(n) time. 
     * Meanwhile, update minimum loss value if the insertion position 
     * is not the smallest one in the tree. 
     * 
     * Go over each house once, each time, binary search will take 
     * O(logn) time, but Insert takes O(n). Therefore, the final 
     * time complexity should be O(n^2), not O(nlogn). 
     */
    private static Int64 MinimumLossCal(int n, Int64[] prices)
    {
        List<Int64> data = new List<Int64>();

        Int64 minLoss = Int64.MaxValue;

        for (int i = n - 1; i >= 0; i--)
        {
            Int64 curPrice = prices[i];
            var index = data.BinarySearch(curPrice);
            if (index < 0)
            {
                int pos = ~index;
                if (pos > 0)
                {
                    Int64 newDiff = curPrice - data[pos - 1];

                    minLoss = (newDiff < minLoss) ? newDiff : minLoss;
                }

                data.Insert(pos, curPrice);
            }

            // if there is one in the binary search tree, then no need to insert the duplicate one in the tree.                
        }

        return minLoss;
    }

With advice from @Nikita B, I did put together a solution using C# List class, and implemented a binary search tree. The time complexity of algorithm is O(nlogn). The C# solution is better than LINQ solution, Test Case #11, #12, #13 still are timeout, but Test Case #14, #15 works fine. Will continue to seek advice and do some research.

With advice from @Nikita B, I did put together a solution using C# List class, and implemented a binary search tree. The time complexity of algorithm is still O(n^2). The C# solution is better than LINQ solution, Test Case #11, #12, #13 still are timeout, but Test Case #14, #15 works fine. Will continue to seek advice and do some research. List Insert API takes O(n) time, since it is a linked list, not a binary search tree.