2017年9月24日 星期日

[演算法] 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;
    }
  }

  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

資料來源

Share:

0 意見:

張貼留言