一次賺最多

思路是記錄歷史低點,每次都計算交易獲利,只留下最大獲利記錄 O(n):

p.s. 下面有個小技巧是利用 Integer.MAX_VALUE來避開需要跳過第一個元素的囉唆

後記

看了一下討論,發現有人提到這題也可以用 max subarray 的貪婪解法來套用

回去再寫一遍 max subarray 解法:

p.s. 上面小技巧 sum = Math.max(sum, 0) 等價 if (sum < 0) sum = 0

拿來套用了話,也就是紀錄累績連續交易獲利,一旦虧損就歸零重算,取出曾經累績連續交易獲利最多記錄:

挺特別的,因為概念是不論一次交易與連續交易,獲利最高點是不變的。

下一集:

狀態機