# leetcode 121. Best Time to Buy and Sell Stock

121. Best Time to Buy and Sell Stock

309. Best Time to Buy and Sell Stock with Cooldown

## 1. brute force裸写

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])

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]


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

prince [7, 1, 5, 3, 6, 4]

gain [-6, 4, -2, 3, -2]

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))