思路概述
I、只许购买一次股票。遍历所有时间的股票价格，以当前股票价格之前出现过的最低价作为买入价，并计算出当天价格出售的收益，与曾经的最大收益对比，遍历完即可的得到最大可能收益；
II、交易次数不限，但每次只能持有一只股票。就可以用贪心法，只要当天价格高于前一天，就加入到收益之中去；
III、最多两次购买股票。动态规划问题，可以以第i天未分界点，计算前面的单次股票最大收益和后面股票的最大收益，然后求两者和的最大值作为最终的收益。
IV、特殊的动态规划问题，Local[i][j]表示在到达第i天时最多可进行j次交易并且最后一次交易在最后一天卖出的最大利润，此为局部最优。Global[i][j]为在到达第i天时最多可进行j次交易的最大利润，此为全局最优。特别注意，递推公式的max函数实际上代表了对过去状态产生的多个结果进行择优。
特殊动态规划问题公式
Local[i][j] = max(Local[i-1][j], Global[i-1][j-1]) + difference(状态增益值)
Global[i][j] = max(Local[i][j], Global[i-1][j])
理解公式很重要。
I
描述
假设有一个数组，它的第i个元素是一支给定的股票在第i天的价格。如果你最多只允许完成一次交易(例如,一次买卖股票),设计一个算法来找出最大利润。
样例
给出一个数组样例 [3,2,3,1,2], 返回 1
代码
class Solution:
"""
@param prices: Given an integer array
@return: Maximum profit
"""
def maxProfit(self, prices):
maxProfit = 0
if len(prices) == 0:
return maxProfit
minPrice = prices[0]
for i in range(1, len(prices)):
minPrice = min(minPrice, prices[i])
maxProfit = max(maxProfit, prices[i]-minPrice)
return maxProfit
II
描述
假设有一个数组，它的第i个元素是一个给定的股票在第i天的价格。设计一个算法来找到最大的利润。你可以完成尽可能多的交易(多次买卖股票)。然而,你不能同时参与多个交易(你必须在再次购买前出售股票)。
样例
给出一个数组样例[2,1,2,0,1], 返回 2
代码
class Solution:
"""
@param prices: Given an integer array
@return: Maximum profit
"""
def maxProfit(self, prices):
# write your code here
maxProfit = 0
if len(prices) == 0:
return maxProfit
for i in range(1, len(prices)):
maxProfit = maxProfit + max(0, prices[i]-prices[i-1])
return maxProfit
III
描述
假设你有一个数组，它的第i个元素是一支给定的股票在第i天的价格。设计一个算法来找到最大的利润。你最多可以完成两笔交易。
样例
给出一个样例数组 [4,4,6,1,1,4,2,5], 返回 6
代码
class Solution:
"""
@param prices: Given an integer array
@return: Maximum profit
"""
def maxProfit(self, prices):
# write your code here
if len(prices) <= 1:
return 0
ProfitLift = [0 for i in range(len(prices))]
ProfitRight = [0 for i in range(len(prices))]
minPrice = prices[0]
for i in range(1, len(ProfitLift)):
minPrice = min(minPrice, prices[i])
ProfitLift[i] = max(ProfitLift[i-1], max(ProfitLift[i], prices[i]-minPrice))
maxPrice = prices[-1]
for i in reversed(range(1, len(ProfitRight))):
maxPrice = max(maxPrice, prices[i])
ProfitRight[i-1] = max(ProfitRight[i], max(ProfitRight[i-1], maxPrice-prices[i-1]))
result = 0
for i in range(0, len(prices)):
result = max(result, ProfitLift[i] + ProfitRight[i])
return result
IV
描述
假设你有一个数组，它的第i个元素是一支给定的股票在第i天的价格。
设计一个算法来找到最大的利润。你最多可以完成 k 笔交易。
样例
给定价格 = [4,4,6,1,1,4,2,5], 且 k = 2, 返回 6.
挑战
O(nk) 时间序列。
代码
class Solution:
"""
@param nums: A list of integers
@param k: An integer denote to find k non-overlapping subarrays
@return: An integer denote the sum of max k non-overlapping subarrays
"""
def maxProfit(self, K, prices):
# write your code here
if len(prices) <=1:
return 0
elif K >= len(prices):
result = 0
for i in range(1, len(prices)):
result = max(prices[i]-prices[i-1], 0) + result
return result
else:
Local = [[0 for i in range(K + 1)] for i in range(len(prices) + 1)]
Global = [[0 for i in range(K + 1)] for i in range(len(prices) + 1)]
for i in range(1, len(prices)+1):
for j in range(1, K+1):
if j*2 > i:
Local[i][j] = 0
Global[i][j] = 0
else:
Local[i][j] = max(Local[i-1][j], Global[i-1][j-1]) + (prices[i-1] - prices[i-2])
Global[i][j] = max(Local[i][j], Global[i-1][j])
return max(Global[-1])
(优化空间使用)
class Solution:
"""
@param K: An integer
@param prices: An integer array
@return: Maximum profit
"""
def maxProfit(self, K, prices):
# write your code here
if len(prices) <=1:
return 0
elif K >= len(prices):
result = 0
for i in range(1, len(prices)):
result = max(prices[i]-prices[i-1], 0) + result
return result
else:
Local = [[0 for j in range(K+1)] for i in range(2)]
Global = [[0 for j in range(K+1)] for i in range(2)]
for i in range(1, len(prices)+1):
for j in range(1, K+1):
if j*2 >i:
Local[1][j] = 0
Global[1][j] = 0
else:
Local[1][j] = max(Local[0][j], Global[0][j-1]) + (prices[i-1] - prices[i-2])
Global[1][j] = max(Local[1][j], Global[0][j])
for j in range(1, K+1):
Local[0][j] = Local[1][j]
Global[0][j] = Global[1][j]
return max(Global[0])
题目来源
https://www.lintcode.com/problem/best-time-to-buy-and-sell-stock-i/description
https://www.lintcode.com/problem/best-time-to-buy-and-sell-stock-ii/description
https://www.lintcode.com/problem/best-time-to-buy-and-sell-stock-iii/description
https://www.lintcode.com/problem/best-time-to-buy-and-sell-stock-iv/description
