121. Best Time to Buy and Sell Stock
309. Best Time to Buy and Sell Stock with Cooldown
题目大意：给定一个数组表示每天的股票价格，求最大的收益
解题思路： 经典一维动态规划题。在最低价的时候购买，然后在第i天出售。因为这个题目允许回看最低的价格，所以能够找到所有天数的最低价格，然后用当前价格减去最低价格得到profit，再找出最大的profit：比较当前的profit跟到前一天位置最高profit取最大值
1. brute force裸写
时间复杂度是O(n^2).
这个题如果直接裸写的话，会超时。200个测试中，199个跑过了，最后一个超时，所以这个办法不可行
class Solution(object):
def maxProfit(self, prices):
ans = 0
for i in range(len(prices) - 1):
for j in range(i, len(prices)):
if ans < prices[j] - prices[i]:
ans = prices[j] - prices[i]
return ans
2. 动态规划
buy price: prices[i] is the min(prices[k], k <= i)
sell price: prices[j] is the max(prices[k], k >= j)
L[i]: lowest price up to i_th day
P[i]: max profit up to i_th day
P[i] = max(P[i - 1], prices[i] - L[i])
在最低价的时候购买，然后在第i天出售。因为这个题目允许回看最低的价格，所以能够找到所有天数的最低价格，然后用当前价格减去最低价格得到profit，再找出最大的profit：比较当前的profit跟到前一天位置最高profit取最大值
def maxProfit(self, prices):
n = len(prices)
if n == 0:
return 0
p = [0 for _ in range(n)]
l = [0 for _ in range(n)]
l[0] = prices[0]
for i in range(1, n):
l[i] = min(l[i - 1], prices[i])
p[i] = max(prices[i] - l[i], p[i - 1])
return p[n - 1]
进一步，因为l和p只跟上一步有关系，所有可以进一步压缩空间成常量。
def maxProfit(self, prices):
n = len(prices)
if n == 0:
return 0
p = 0
l = prices[0]
for i in range(1, n):
l = min(l, prices[i])
p = max(prices[i] - l, p)
return p
3. Reduce to LC 53 Maximum Subarray
如果前一天买，后一天卖出，那么当天股价跟前一天股价的差价即为当天的盈利。从所有的盈利当中找出一个连续子集，这个连续子集的最大和就是最大的盈利值。求取最大连续子集的和的过程即是LC 53 Maximum Subarray.
prince [7, 1, 5, 3, 6, 4]
gain [-6, 4, -2, 3, -2]
所以最大盈利是 4 - 2 + 3 = 5
def maxProfit(self, prices):
n = len(prices)
if n == 0 or n == 1:
return 0
gain = [0 for _ in range(n - 1)]
for i in range(n - 1):
gain[i] = prices[i + 1] - prices[i]
def maxSubarray(nums):
n = len(nums)
if n == 1:
return nums[0]
p = [-float('inf') for _ in range(n)]
p[0] = nums[0]
for i in range(n):
p[i] = max(p[i - 1] + nums[i], nums[i])
return max(p)
return max(0, maxSubarray(gain))