[LeetCode] 121. Best Time to Buy and Sell Stock

轉自LeetCode

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.

Example 1:

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)

Example 2:

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

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

<Solution>

這題白話的來看，就是要把一個 array 的最大值和最小值的差值求出來

但有個地方要注意，最大最小值是有時間觀念在的

因為題目有說，只能先買再賣

所以使用 sort 來找出最大最小值，會打亂時間順序

這邊的解題想法會是這樣

• 記錄目前的最小值。如果當下的數字比最小值大，則計算其差值

因為只能先買後賣，所以最佳的買點一定會先出現

這樣只要 one-pass 就可以找出答案

code 如下 (參考資料)
c++

kotlin

這題還有另一種解法，運用到動態規劃的概念

用兩個變數，分別是 localMax 和 globalMax 來記錄局部和全局的最大獲利

localMax 代表的是，在某個點賣出去的最大獲利

globalMax 則是所有 localMax 當中，最大的那一個值

code 如下(參考資料)