using System;

public class Program

{

    public static void Main()

    {

        int[] prices = new[] {7,1,5,3,6,4};

        //int result = MaxProfit(prices);

        int result = MaxProfitBest(prices);

        Console.WriteLine(result);

    }

    public static int MaxProfit(int[] prices) {

        int maxProfit = 0;

        // loop through array until last buying opportunity (second to last value in array)

        for (int i = 0; i < prices.Length - 1; i++)

        {

            // if current is less than next, check remaining for potential profit

            if (prices[i] < prices[i + 1])

            {

                // check remaining for highest value

                for (int j = i + 1; j < prices.Length && prices[j] > prices[i]; j++)

                {

                    if (prices[j] - prices[i] > maxProfit)

                        maxProfit = prices[j] - prices[i];

                }

            }

        }

​

        return maxProfit;

    }

    public static int MaxProfitBest(int[] prices) {

        if(prices == null || prices.Length < 2) return 0;

        int res = 0;

        int min = prices[0];

        for(int i = 0; i < prices.Length; i++){

            // assign min the less of min and current price

            min = Math.Min(min, prices[i]);

            // assign the greater of res and current price - min

            res = Math.Max(res, prices[i] - min);

        }

        return res;

    }

​

}