PJCHENder 未整理筆記

[演算法] Max Stock Profit

2017-09-26

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

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

1
2
3
4
5
6
7
8
9
10
function maxStockProfit(pricesArr) {
// declaring variables
let maxProfit = -1;
let currentProfit = 0;
let buyPrice = 0;
let sellPrice = 0;
let changeBuyPrice = true;

// ...
}

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
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;
}
}
// ...
}

完整程式碼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
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

資料來源

掃描二維條碼,分享此文章