Calculating the most profit from an array of stock prices

Question

I'm a newbie learning how to code, and I am trying to find the most efficient way to calculate the most profit from an array of stock prices. For a given array,I have a list of stock prices over n days. So for {1, 4, 5, 100}, my maxProfit would be 99 (100-1). The rule for maxProfit would be the greatest difference between two numbers in the Array where you cannot count backwards in the array.

I'm able to get the right solution, but it's not the most efficient. I'm striving for my solution to be \$O(n)\$. At the moment given that single loop and then the Max function, my solution is n^2 because there are two loops. Is there a way I can break it down to just one?

var stockPrices = new List<int>() { 30, 50, 3, 2, 1, 1, 10, 25, 2, 10 };

var maxProfit = 0;
for(int x = 0; x < stockPrices.ToArray().Length; x++)
{
    int maxValue = stockPrices.Max();
    int maxIndex = stockPrices.IndexOf(maxValue);

    var allValuesToTheLeftOftheMax = stockPrices.GetRange(0, maxIndex);

    //Find the min value
    if (maxIndex == 0)
    {
        stockPrices.Remove(maxValue);
    }
    else
    {
        int minValue = allValuesToTheLeftOftheMax.Min();

        //Get the max profit 
        if (maxProfit < maxValue - minValue)
        {
            maxProfit = maxValue - minValue;
        }

        stockPrices.Remove(maxValue);
    }
    Console.WriteLine("Max profit currently is {0}", maxProfit);
}

Console.WriteLine("Final max profit is {0}", maxProfit);
Console.ReadLine();

Answer 1

The following implementation will be \$O(n)\$.

public static int getMaxProfit(int[] stockPricesYesterday) {
    // make sure we have at least 2 prices
    if (stockPricesYesterday.length < 2) {
        throw new IllegalArgumentException("Getting a profit requires at least 2 prices");
    }

    // we'll greedily update minPrice and maxProfit, so we initialize
    // them to the first price and the first possible profit
    int minPrice = stockPricesYesterday[0];
    int maxProfit = stockPricesYesterday[1] - stockPricesYesterday[0];

    // start at the second (index 1) time
    // we can't sell at the first time, since we must buy first,
    // and we can't buy and sell at the same time!
    // if we started at index 0, we'd try to buy *and* sell at time 0.
    // this would give a profit of 0, which is a problem if our
    // maxProfit is supposed to be *negative*--we'd return 0.
    for (int i = 1; i < stockPricesYesterday.length; i++) {
        int currentPrice = stockPricesYesterday[i];

        // see what our profit would be if we bought at the
        // min price and sold at the current price
        int potentialProfit = currentPrice - minPrice;

        // update maxProfit if we can do better
        maxProfit = Math.max(maxProfit, potentialProfit);

        // update minPrice so it's always
        // the lowest price we've seen so far
        minPrice = Math.min(minPrice, currentPrice);
    }

    return maxProfit;
}