Best time to buy and sell 📈 (easy)

This problem asks to find the highest profit given a list of daily prices. We are provided with an array of integers and have to find the highest possible buy-sell combination during the period of time in the array.

The main technique of this algorithm is to use Math.max method to compare the profits of the combinations and keep the highest one.

const maxProfit = (prices) => {

    if (prices.length === 0){
        return 0
    }
    let current = 0
    let max = 0
    for(let i = 0; i<prices.length; i++){

        for(let j = i+1; j<prices.length; j++){
        // O(n^2) nested loop
        // inner loop on i+1 to always compare to next elements
            if(prices[j] - prices[i] > 0){
                current = prices[j] - prices[i]
            }
        max = Math.max(current, max) 
        // compare profits save higher
        }
    }
    return max
};

We use a nested loop that starts at i+1 so we can compare the future days' price to the current day's price.

Also, we use two variables to store the profits current (only when the difference is positive so there is profit) and max, and with the Math.max method, only keep the highest of the two.

Feel free to reach out on LinkedIn and Twitter!

Comments

[Kai]

Thanks for your post! I've tried finding a simpler solution:

const maxProfit = (prices) => {
  if (prices.length === 0) return 0;

  // Calculate maximum profit for each price.
  const profits = prices.map((price, i) => {
    // Find maximum price, ignoring prices before our current price.
    const max = Math.max(...prices.slice(i));
    return max - price;
  });

  // Return maximum profit.
  return Math.max(...profits);
};

I did not test for performance, though. Nevertheless, I think it's more readable.

[Santiago Salazar Pavajeau]

I think your solution is very clever using the spread operator to find the highest profit. I tried to share a solution where the step-by-step is very clear, so it can be rewritten in any language! Thanks again for yours, it is great!

[Kai]

Thank you :)