Return to Answer

###Use GetViewBetween()###

I was able to take your SortedSet solution and get it to work by using the GetViewBetween() method. The idea is that given a current minimum loss and a new price, you are looking in the set for any price that falls in the range: price - minLoss + 1 to price - 1. You can use GetViewBetween() to find the subset that falls in that range, and take the Max of that subset. This effectively does the same that floor() does for a java TreeSet.

I compared this solution to the List + BinarySearch() solution that you posted in an answer (which you said was your fastest). On an input of 200000 random values, mine completed in 0.26 seconds compared to 4.8 seconds, for an 18x speedup.

###Function rewrite###

Here is your function rewritten using GetViewBetween():

 private static Int64 MinimumLossCal(int n, Int64[] prices)
 {
 SortedSet<Int64> data = new SortedSet<Int64>();
 Int64 minLoss = Int64.MaxValue;
 for (int i = n - 1; i >= 0; i--)
 {
 Int64 curPrice = prices[i];
 Int64 minVal = curPrice - minLoss + 1;
 Int64 maxVal = curPrice - 1;
 if (minVal <= maxVal)
 {
 var smaller = data.GetViewBetween(minVal, maxVal);
 if (smaller.Any())
 {
 minLoss = curPrice - smaller.Max;
 }
 }
 data.Add(curPrice);
 }
 return minLoss;
 }

Note that the problem stated that the prices would always be >= 1, which prevents minVal from underflowing past Int64.MinValue.

Use GetViewBetween()

I was able to take your SortedSet solution and get it to work by using the GetViewBetween() method. The idea is that given a current minimum loss and a new price, you are looking in the set for any price that falls in the range: price - minLoss + 1 to price - 1. You can use GetViewBetween() to find the subset that falls in that range, and take the Max of that subset. This effectively does the same that floor() does for a java TreeSet.

I compared this solution to the List + BinarySearch() solution that you posted in an answer (which you said was your fastest). On an input of 200000 random values, mine completed in 0.26 seconds compared to 4.8 seconds, for an 18x speedup.

Function rewrite

Here is your function rewritten using GetViewBetween():

 private static Int64 MinimumLossCal(int n, Int64[] prices)
 {
 SortedSet<Int64> data = new SortedSet<Int64>();
 Int64 minLoss = Int64.MaxValue;
 for (int i = n - 1; i >= 0; i--)
 {
 Int64 curPrice = prices[i];
 Int64 minVal = curPrice - minLoss + 1;
 Int64 maxVal = curPrice - 1;
 if (minVal <= maxVal)
 {
 var smaller = data.GetViewBetween(minVal, maxVal);
 if (smaller.Any())
 {
 minLoss = curPrice - smaller.Max;
 }
 }
 data.Add(curPrice);
 }
 return minLoss;
 }

Note that the problem stated that the prices would always be >= 1, which prevents minVal from underflowing past Int64.MinValue.