121. Best Time to Buy and Sell Stock (Easy)
給一列股票價格，問買賣不超過1次的情況下最多賺多少
122. Best Time to Buy and Sell Stock III (Medium)
給一列股票價格，問無限次買賣的情況下最多賺多少（但手里同一時刻只能持有一份股票）
123. Best Time to Buy and Sell Stock III (Hard)
給一列股票價格，問買賣不超過2次的情況下最多賺多少
188. Best Time to Buy and Sell Stock IV (Hard)
給一列股票價格，問買賣不超過k次的情況下最多賺多少
121, 123和188類似，都是DP思想，remain[j]：已經買入j次之后最多手頭剩下的錢，profit[j]：已經賣出j次之后最多賺了多少，注意賣出前必須要先買入，188注意特判len(prices)=1的情況
122貪心，預處理i和i+1天之間的價差，有的賺就都加上
1 #121
2 #Runtime: 869 ms
3 #Memory Usage: 22.5 MB
4
5 class Solution(object):
6 def maxProfit(self, prices):
7 """
8 :type prices: List[int]
9 :rtype: int
10 """
11 remain = 0
12 profit = 0
13 remain = prices[0]
14 for i in range(1, len(prices)):
15 remain = min(remain, prices[i])
16 profit = max(profit, prices[i] - remain)
17 return profit
1 #122
2 #Runtime: 48 ms
3 #Memory Usage: 14.8 MB
4
5 class Solution(object):
6 def maxProfit(self, prices):
7 """
8 :type prices: List[int]
9 :rtype: int
10 """
11 profit = []
12 for i in range(len(prices) - 1):
13 profit.append(prices[i + 1] - prices[i])
14 ans = 0
15 for i in profit:
16 if i > 0:
17 ans += i
18 return ans
19
1 #123
2 #Runtime: 1075 ms
3 #Memory Usage: 25 MB
4
5 class Solution(object):
6 def maxProfit(self, prices):
7 """
8 :type prices: List[int]
9 :rtype: int
10 """
11 remain = [0, -sys.maxint, -sys.maxint]
12 profit = [0, -sys.maxint, -sys.maxint]
13
14 for i in range(0, len(prices)):
15 for j in range(1, 3):
16 remain[j] = max(remain[j], profit[j - 1] - prices[i])
17 profit[j] = max(profit[j], remain[j] + prices[i])
18 return max(profit)
1 #188
2 #Runtime: 250 ms
3 #Memory Usage: 13.3 MB
4
5 class Solution(object):
6 def maxProfit(self, k, prices):
7 """
8 :type k: int
9 :type prices: List[int]
10 :rtype: int
11 """
12 remain = [-sys.maxint] * (len(prices) + 1)
13 profit = [-sys.maxint] * (len(prices) + 1)
14 remain[0] = 0
15 profit[0] = 0
16 for i in range(0, len(prices)):
17 for j in range(1, min(len(prices) + 1, k + 1)):
18 remain[j] = max(remain[j], profit[j - 1] - prices[i])
19 profit[j] = max(profit[j], remain[j] + prices[i])
20 return max(profit)