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)