Best Time to Buy and Sell Stock

Say you have an array for which the ith element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Example1:

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

max. difference = 6-1 = 5 (not 7-1 = 6, as selling price needs to be larger than buying price)

Example2:

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

In this case, no transaction is done, i.e. max profit = 0.

提示	解題應用
Array	Array/Slice
DynamicProgramming	規律觀查

Default:

func maxProfit(prices []int) int {

}

解答思路:

此題意思是給予一段每日股票票價的陣列，要求你來找出賺取最大差價的利潤，不過在賺錢之前當然要先把股票買好，這樣在最大差價的時候才能把股票給賣掉，意思就是說如果你在第三天才買股票，就算前兩天的賣價不錯，你也沒辦法販賣，因為當下你手上根本就沒有半張股票，就只能找第三天之後的股價來賣，所以這題的目標是要你找出在適當時機購買並販售出去的最大利潤，關鍵在於邊找最大利潤的同時，如果發現有更便宜的股價想要賺買並嘗試尋找利潤時，此時記得將先前找到的最佳出售價格給歸0，畢竟買了才能拿來賣，理所當然出售價格要重新開始找。

程式碼解說:

這邊先把空陣列的狀況給過濾掉，以方便我們在一開始就先把第一天的價格初始化買價與賣價，如此一來就能依據第一天的價格來判斷後續價格相對於買與賣究竟是高還是低，所以再來迴圈取出價格時就是從index為1，也就是第二天開始取出，正如先前所說的，如果發現較低的價格能購入時，要記得把先前找到的最佳賣價給歸0以利重新尋找，如果發現的是較高的賣價時，因為先前就已經決定好買價了，所以就不需要客氣直接賣了，不過前提題不做虧本生意，當然賣價要比買價高才行，剩下的就是與先前的價差來比較是否為最大利潤

if len(prices) == 0 {
	return 0
}
var maxProfit int
buyPrice := prices[0]
sellPrice := prices[0]
for _, v := range prices[1:] {
	if v < buyPrice {
		buyPrice = v
		sellPrice = 0
	}
	if v > sellPrice {
		sellPrice = v
		if buyPrice < sellPrice && sellPrice-buyPrice > maxProfit {
			maxProfit = sellPrice - buyPrice
		}
	}
}
return maxProfit

完整程式碼:

func maxProfit(prices []int) int {
	if len(prices) == 0 {
		return 0
	}
	var maxProfit int
	buyPrice := prices[0]
	sellPrice := prices[0]
	for _, v := range prices[1:] {
		if v < buyPrice {
			buyPrice = v
			sellPrice = 0
		}
		if v > sellPrice {
			sellPrice = v
			if buyPrice < sellPrice && sellPrice-buyPrice > maxProfit {
				maxProfit = sellPrice - buyPrice
			}
		}
	}
	return maxProfit
}

總結:

給予一段每日股票票價的陣列，要求找出賺取最大差價的利潤，關鍵在於邊找利潤的同時，如果發現有更便宜的股價想要賺買並嘗試尋找最大利潤時，此時記得將先前找到的最佳出售價格給歸0，畢竟買了才能拿來賣，理所當然出售價格要重新開始找。