Best Time to Buy and Sell Stock

Input: [7, 1, 5, 3, 6, 4]
Output: 7

Input: [1, 2, 3, 4, 5]
Output: 4

Input: [7, 6, 4, 3, 1]
Output: 0

/**
 * Finds the maximum profit from selling and buying the stocks.
 * ACCUMULATOR APPROACH.
 *
 * @param {number[]} prices - Array of stock prices, i.e. [7, 6, 4, 3, 1]
 * @param {function(): void} visit - Visiting callback to calculate the number of iterations.
 * @return {number} - The maximum profit
 */
const accumulatorBestTimeToBuySellStocks = (prices, visit = () => {}) => {
  visit();
  let profit = 0;
  for (let day = 1; day < prices.length; day += 1) {
    visit();
    // Add the increase of the price from yesterday till today (if there was any) to the profit.
    profit += Math.max(prices[day] - prices[day - 1], 0);
  }
  return profit;
};

export default accumulatorBestTimeToBuySellStocks;

/**
 * Finds the maximum profit from selling and buying the stocks.
 * DYNAMIC PROGRAMMING APPROACH.
 *
 * @param {number[]} prices - Array of stock prices, i.e. [7, 6, 4, 3, 1]
 * @param {function(): void} visit - Visiting callback to calculate the number of iterations.
 * @return {number} - The maximum profit
 */
const dpBestTimeToBuySellStocks = (prices, visit = () => {}) => {
  visit();
  let lastBuy = -prices[0];
  let lastSold = 0;

  for (let day = 1; day < prices.length; day += 1) {
    visit();
    const curBuy = Math.max(lastBuy, lastSold - prices[day]);
    const curSold = Math.max(lastSold, lastBuy + prices[day]);
    lastBuy = curBuy;
    lastSold = curSold;
  }

  return lastSold;
};

export default dpBestTimeToBuySellStocks;

/**
 * Finds the maximum profit from selling and buying the stocks.
 * DIVIDE & CONQUER APPROACH.
 *
 * @param {number[]} prices - Array of stock prices, i.e. [7, 6, 4, 3, 1]
 * @param {function(): void} visit - Visiting callback to calculate the number of iterations.
 * @return {number} - The maximum profit
 */
const dqBestTimeToBuySellStocks = (prices, visit = () => {}) => {
  /**
   * Recursive implementation of the main function. It is hidden from the users.
   *
   * @param {boolean} buy - Whether we're allow to sell or to buy now
   * @param {number} day - Current day of trading (current index of prices array)
   * @returns {number} - Max profit from buying/selling
   */
  const recursiveBuyerSeller = (buy, day) => {
    // Registering the recursive call visit to calculate the complexity.
    visit();

    // Quitting the recursion if this is the last day of trading (prices array ended).
    if (day === prices.length) {
      return 0;
    }

    // If we're buying - we're loosing money (-1), if we're selling we're getting money (+1).
    const operationSign = buy ? -1 : +1;
    return Math.max(
      // Option 1: Don't do anything.
      recursiveBuyerSeller(buy, day + 1),
      // Option 2: Sell or Buy at the current price.
      operationSign * prices[day] + recursiveBuyerSeller(!buy, day + 1),
    );
  };

  const buy = true;
  const day = 0;

  return recursiveBuyerSeller(buy, day);
};

export default dqBestTimeToBuySellStocks;

/**
 * Finds the maximum profit from selling and buying the stocks.
 * PEAK VALLEY APPROACH.
 *
 * @param {number[]} prices - Array of stock prices, i.e. [7, 6, 4, 3, 1]
 * @param {function(): void} visit - Visiting callback to calculate the number of iterations.
 * @return {number} - The maximum profit
 */
const peakvalleyBestTimeToBuySellStocks = (prices, visit = () => {}) => {
  visit();
  let profit = 0;
  let low = prices[0];
  let high = prices[0];

  prices.slice(1).forEach((currentPrice) => {
    visit();
    if (currentPrice < high) {
      // If price went down, we need to sell.
      profit += high - low;
      low = currentPrice;
      high = currentPrice;
    } else {
      // If price went up, we don't need to do anything but increase a high record.
      high = currentPrice;
    }
  });

  // In case if price went up during the last day
  // and we didn't have chance to sell inside the forEach loop.
  profit += high - low;

  return profit;
};

export default peakvalleyBestTimeToBuySellStocks;