3
\$\begingroup\$

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();
\$\endgroup\$
  • \$\begingroup\$ Makes not sense to me. What is the rule for maxProfit? stockPrices.Max is O(n) alone. Why ToList() when it already is a list. That code would not return the correct answer for {1, 4, 5, 100}. \$\endgroup\$ – paparazzo Jul 13 '17 at 18:51
  • \$\begingroup\$ Sorry, the program spits out 99, which is the MaxProfit. And I edited out the ToList, since it was not necessary. I guess now that I have the Max(), in my loop then this code is n^2? How do I get it down to n? \$\endgroup\$ – JohnnyTheJet Jul 13 '17 at 19:04
  • \$\begingroup\$ You still have not stated the rule. Fix the question. This is a sloppy question. \$\endgroup\$ – paparazzo Jul 13 '17 at 19:06
  • 1
    \$\begingroup\$ you cannot count backwards in the array - who says that? Why shouldn't you? \$\endgroup\$ – t3chb0t Jul 13 '17 at 19:34
  • 2
    \$\begingroup\$ If you think about Sunday, Monday, Tuesday, the stock price on Sunday is 100, Monday it drops to 1 and Tuesday it stays on 1, your maxProfit is 0, not 99. because you can't teleport back in time. Maybe, I'm not using the right words. \$\endgroup\$ – JohnnyTheJet Jul 13 '17 at 19:38
3
\$\begingroup\$

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;
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.