0121. Best Time to Buy and Sell Stock (Easy)

Question

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 (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Note that you cannot sell a stock before you buy one.

Example 1

1
2
3
4

Input: [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
             Not 7-1 = 6, as selling price needs to be larger than buying price.

Example 2

1
2
3

Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.

分析/解題

買股票啦XD~題目給定一個陣列，第i個元素代表day i的股價。
如果你只被允許完成一次交易(買一次然後賣一次)，
嘗試找到最大的利潤為何。

我們假定我們在某個時間點買了股票，
那獲得的利潤每隔一天，就會變動這兩天的差價值。
我們可以將當下的利潤定為cur，那麼cur不論從哪開始必定為0。
(當天買當天賣)

假定有一天股價低於 我們買的時候的價格，就表示我們買貴 了，
應該要從現在這個點開始一定會比前面那個點還好 ，(買進的價格較低)
我們可以將cur重設為0(從這個點重新出發) 。

反之如果價格比較高的話，我們可以計算現在的利潤，
並和全局最大值比較後再更新全局最大值。
所以每次依序計算現在的利潤決定是否重新選擇出發點，
再處理好全局最大值的紀錄即可解決此題。

這邊Java和Python的程式碼僅差別在設定條件的方式不同而已，
但本質一樣是在處理現有的值 及最大值 這兩項。
讀者可以自行選用處理的方式。

Java

Python

面試實際可能會遇到的問題

「時間/空間複雜度？」
(O(N), O(1)，掃過整個空間一次，除cur跟res外不需其他變數。)

相似及延伸

1.0053. Maximum Subarray 2. Best Time to Buy and Sell Stock系列題(XDDDDD)

Special Thanks suggestions/corrections from viewers:
(歡迎提供意見協助更正歐~)

從LeetCode學演算法，我們下次見囉，掰~