[演算法] Max Stock Profit

此系列筆記主要依照 [Udemy] Learning Algorithms in JavaScript from Scratch by Eric Traub 的課程脈絡加以整理，但部分程式碼是消化後以自己較易理解的方式重新撰寫，因此和原課程內容有些出入。

問題描述

以陣列的方式儲存許多數值，這些數值是各個不同時間點股票的價格，例如，[32, 46, 26, 38, 40, 48, 42]，我們要透過演算法：

1. 找出在哪個時間點買進、哪個時間點賣出可以獲得最高的收益。以剛剛的陣列為例，應該在價格為 26 元時買入、48 元時賣出，這時會獲得 22 元的最高收益。
2. 如果該天沒有獲利的可能則回傳 -1。

演算法實做

在計算最高獲利時有一個重點，就是它是有時間性的，也就是說一定是先買進才能賣出，不可能先賣出，之後才買進。

因此，在我們的演算法中，會先將陣列中的第一個元素當作買進價（buyPrice），然後去和後面的價格做比較：

• 當買進價低於賣出價時，就可以計算看看此時會有多少獲利（currentProfit）
• 當買進價高於賣出價時，把這個賣出價改成新的買進價（changeBuyPrice）

我們先定義在這個含式中會使用到的變數：

function maxStockProfit(pricesArr) {
  // declaring variables
  let maxProfit = -1;
  let currentProfit = 0;
  let buyPrice = 0;
  let sellPrice = 0;
  let changeBuyPrice = true;

  // ...
}

接著要開始去找出獲益最高的組合：

function maxStockProfit(pricesArr) {
  // ...

  /**
   * 找出獲益最高的組合
   **/
  for (let i = 0; i < pricesArr.length; i++) {
    if (changeBuyPrice) {
      buyPrice = pricesArr[i];
    }
    sellPrice = pricesArr[i + 1];

    // 如果賣出價格 >= 買進價格，表示這是可以買入的價格
    // 因為獲利至少 >= 0
    if (sellPrice >= buyPrice) {
      currentProfit = sellPrice - buyPrice;
      if (currentProfit > maxProfit) {
        maxProfit = currentProfit;
      }
      changeBuyPrice = false;
    } else {
      // 如果賣出價格 < 買進價格，表示賣出的話一定會賠錢
      // 所以不能在此時買進
      changeBuyPrice = true;
    }
  }
  // ...
}

完整程式碼

function maxStockProfit(pricesArr) {
  // declaring variables
  let maxProfit = -1;
  let buyPrice = 0;
  let sellPrice = 0;
  let changeBuyPrice = true;

  /**
   * 找出獲益最高的組合
  **/
  for (let i = 0; i < pricesArr.length; i++) {
    if (changeBuyPrice) {
      buyPrice = pricesArr[i];
    }
    sellPrice = pricesArr[i + 1];

    // 如果賣出價格 >= 買進價格，表示獲利至少 >= 0
    // 可以賣出計算獲利
    let currentProfit
    if (sellPrice >= buyPrice) {
      changeBuyPrice = false;
      currentProfit = sellPrice - buyPrice;
      if (currentProfit > maxProfit) {
        maxProfit = currentProfit;
      }
    } else {
      // 如果賣出價格 < 買進價格，表示賣出的話一定會賠錢
      // 所以不能在此時買進
      changeBuyPrice = true;
    }

    // console.log(`buyPrice: ${buyPrice}, sellPrice: ${sellPrice}, currentProfit: ${currentProfit}, maxProfit: ${maxProfit}`)
  }

  return maxProfit;
}


console.log(maxStockProfit([32, 46, 26, 38, 40, 48, 42]))     // 22
console.log(maxStockProfit([10, 18, 4, 5, 9, 6, 16, 12]))     // 12
console.log(maxStockProfit([65, 54, 43, 32, 26, 15]))         // -1

Algorithm: Max Stock Profit @ repl.it

資料來源

• Learning Algorithms in JavaScript from Scratch by Eric Traub @ Udemy