本文共 3109 字，大约阅读时间需要 10 分钟。
题目：
假设有一个数组，它的第i个元素是一支给定的股票在第i天的价格。
如果你最多只允许完成一次交易,设计一个算法来找出最大利润。解法：
该题解法和最大连续子数组和的解法思路是一样的。
1、根据股票的利益意义，想要更多利益则值低时买进，值高时卖出。根据提供的股票价格不方便得出股票价格变化，对原数据进行计算：list[i] - list[i-1] = 股票的变化。变化为正时股票增长（存在利益），变化为负时股票为下跌（无利益）。
2、得到股票的变化值列表，即求最大子数组和，最后得到正解。
代码：时间O(n)，空间O(1)
def maxProfit1(list):
# 算出利益比变化列表
NEW=[]
for i in range(len(list)-1):
NEW.append(list[i+1]-list[i])
# 初始化
imax = 0
temp = 0
# 最大子数组和计算方式
for d in NEW:
if temp + d > 0:
temp += d
else:
temp = 0
# 获取当前最大子数组
imax = max(temp,imax)
return imax
买卖股票的最佳时机—2：
题目：
用一个数组表示股票每天的价格，数组的第i个数表示股票在第i天的价格。
交易次数不限，但一次只能交易一支股票，也就是说手上最多只能持有一支股票，求最大收益。
你可以完成尽可能多的交易(多次买卖股票)。
然而,你不能同时参与多个交易(你必须在再次购买前出售股票)。解法：
贪心算法，买卖次数不限，问题就简单了，只要挣钱就卖出。
代码：时间O(n)，空间O(1)
def maxProfit_2(prices):
max_profit = 0
for i in range(1,len(prices)):
d = prices[i] - prices[i-1]
# 值为正即存在利益
if d > 0 :
max_profit += d
return max_profit
买卖股票的最佳时机—3：
题目：
假设你有一个数组，其中第i 个元素是第i天给定股票的价格。
设计一个算法来找到最大的利润。您最多可以完成两笔交易。 您不可以同时进行多笔交易（即您必须在再次购买之前出售股票）。解法：
其实也就是找到两个最大子数组和，和第一道题差不多。
先求出第一个最大子数组，避开第一个最大子数组的情况下，再求出第二大子数组，再相加即可。
代码1：时间O(n)，空间O(1)
def maxProfit_3_1(prices):
release1 = -999
release2 = -999
hold1 = 0
hold2 = 0
for i in prices:
release2 = max (release2, hold2 + i)
hold2 = max (hold2, release1 - i)
release1 = max (release1, hold1 + i)
hold1 = max (hold1, -i)
return release2
def maxProfit_3_2(prices):
sell = [0]
buy = [0]
plen = len (prices)
minp = prices[0]
maxp = prices[-1]
for i in range (1, plen):
minp, maxp = min (minp, prices[i]), max (maxp, prices[plen - i - 1])
sell.append (max (sell[i - 1], prices[i] - minp))
buy.append (max (buy[i - 1], maxp - prices[plen - i - 1]))
return max (sell[i] + buy[plen - i - 1] for i in range (plen))
买卖股票的最佳时机—4：
题目：
假设你有一个数组，它的第i个元素是一支给定的股票在第i天的价格。
设计一个算法来找到最大的利润。你最多可以完成 k 笔交易。 你不可以同时参与多笔交易(你必须在再次购买前出售掉之前的股票)解法：
将这些关键变量命名为本地利润和全局利润，以使事情更容易理解
代码1：
def maxProfit_4(k,prices):
if not prices: return 0
n = len (prices)
if k >= n // 2:
return sum (
x - y
for x, y in zip (prices[1:], prices[:-1])
if x > y)
profits = [0] * n
for j in range (k):
max_all = max_prev = max_here = 0
for i in range (1, n):
profit = prices[i] - prices[i - 1]
max_here = max (max_here + profit, max_prev + profit, max_prev)
max_prev = profits[i]
profits[i] = max_all = max (max_all, max_here)
return profits[-1]
代码2：
def maxProfit4(self, k, prices):
n = len(prices)
if n < 2:
return 0
if k >= n / 2:
return sum(i - j
for i, j in zip(prices[1:], prices[:-1]) if i - j > 0)
globalMax = [[0] * n for _ in xrange(k + 1)]
for i in xrange(1, k + 1):
# 最大的利润与我的交易和卖出股票在第j天。
localMax = [0] * n
for j in xrange(1, n):
profit = prices[j] - prices[j - 1]
localMax[j] = max(
# 我们以(i - 1)的交易获利最多在(j - 1)天
# 在最后一次交易中，我们每天买进股票(j - 1)，然后在第j日卖出。
globalMax[i - 1][j - 1] + profit,
# 在(j - 1)天内，我们以(i - 1)的转换期取得了最大的利润。
# 最后一次交易，我们在j日买进股票，在同一天卖出，所以我们有0利润，显然我们不需要加它。
globalMax[i - 1][j - 1], # + 0,
# 我们已在(j - 1)天内赢利。
# 我们想取消那天(j - 1)的销售，在j日卖出。
localMax[j - 1] + profit)
globalMax[i][j] = max(globalMax[i][j - 1], localMax[j])
return globalMax[k][-1]
有不明白的情况以下链接。
如上案例参考：https://leetcode.com/problemset/all/?search=Best%20Time%20to%20Buy%20and%20Sell%20Stock
转载地址：http://agkii.baihongyu.com/