题目均摘自leetcode，分为以下五题（买卖股票系列）。
- 121 Best Time to Buy and Sell Stock
- 122 Best Time to Buy and Sell Stock II
- 123 Best Time to Buy and Sell Stock III
- 188 Best Time to Buy and Sell Stock IV
- 309 Best Time to Buy and Sell Stock with Cooldown
121. Best Time to Buy and Sell Stock (Easy)
题目描述：只进行一次交易。
只要记录前面的最小价格，将这个最小价格作为买入价格，然后将当前的价格作为售出价格，查看当前收益是不是最大收益。
public int maxProfit(int[] prices) {
int n = prices.length;
if (n == 0) return 0;
int soFarMin = prices[0];
int max = 0;
for (int i = 1; i < n; i++) {
if (soFarMin > prices[i]) soFarMin = prices[i];
else max = Math.max(max, prices[i] - soFarMin);
}
return max;
}
122. Best Time to Buy and Sell Stock II
无数次购买售出
public int maxProfit(int[] prices) {
int max = 0;
for (int i = 0; i < prices.length -1; i++){
if (prices[i+1] > prices[i]) max += prices[i+1] - prices[i];
}
return max;
}
123. Best Time to Buy and Sell Stock III (Hard)
只能进行两次的股票交易 
class Solution:
"""
@param prices: Given an integer array
@return: Maximum profit
"""
def maxProfit(self, prices):
n = len(prices)
K = 2
# corner case
if n == 0:
return 0
# main part
dp = [[0] * n for _ in range(K + 1)]
for i in range(1, K + 1):
max_diff = float('-inf')
for j in range(1, n):
max_diff = max(max_diff, dp[i - 1][j - 1] - prices[j - 1])
dp[i][j] = max(dp[i][j - 1], prices[j] + max_diff)
return dp[K][n - 1]
public int maxProfit(int[] prices) {
int firstBuy = Integer.MIN_VALUE, firstSell = 0;
int secondBuy = Integer.MIN_VALUE, secondSell = 0;
for (int curPrice : prices) {
if (firstBuy < -curPrice) {
firstBuy = -curPrice;
}
if (firstSell < firstBuy + curPrice) {
firstSell = firstBuy + curPrice;
}
if (secondBuy < firstSell - curPrice) {
secondBuy = firstSell - curPrice;
}
if (secondSell < secondBuy + curPrice) {
secondSell = secondBuy + curPrice;
}
}
return secondSell;
}
只能进行 k 次的股票交易
- Best Time to Buy and Sell Stock IV (Hard)
public int maxProfit(int k, int[] prices) {
int n = prices.length;
if (k >= n / 2) { // 这种情况下该问题退化为普通的股票交易问题
int maxProfit = 0;
for (int i = 1; i < n; i++) {
if (prices[i] > prices[i - 1]) {
maxProfit += prices[i] - prices[i - 1];
}
}
return maxProfit;
}
int[][] maxProfit = new int[k + 1][n];
for (int i = 1; i <= k; i++) {
int localMax = maxProfit[i - 1][0] - prices[0];
for (int j = 1; j < n; j++) {
maxProfit[i][j] = Math.max(maxProfit[i][j - 1], prices[j] + localMax);
localMax = Math.max(localMax, maxProfit[i - 1][j] - prices[j]);
}
}
return maxProfit[k][n - 1];
}
需要冷却期的股票交易
- Best Time to Buy and Sell Stock with Cooldown(Medium)
题目描述：交易之后需要有一天的冷却时间。
public class Solution {
/**
* @param prices: a list of integers
* @return: return a integer
*/
public int maxProfit(int[] prices) {
// write your code here
if(prices == null || prices.length < 2) return 0;
int[] sell = new int[prices.length];
int[] buy = new int[prices.length];
sell[0] = 0;
buy[0] = -prices[0];
for(int i = 1; i < prices.length; i++)
{
sell[i] = Math.max(sell[i-1], buy[i-1] + prices[i]);
buy[i] = Math.max(buy[i-1], (i>1?sell[i-2]:0) - prices[i]);
}
return sell[prices.length-1];
}
}
public int maxProfit(int[] prices) {
if (prices == null || prices.length == 0) {
return 0;
}
int N = prices.length;
int[] buy = new int[N];
int[] s1 = new int[N];
int[] sell = new int[N];
int[] s2 = new int[N];
s1[0] = buy[0] = -prices[0];
sell[0] = s2[0] = 0;
for (int i = 1; i < N; i++) {
buy[i] = s2[i - 1] - prices[i];
s1[i] = Math.max(buy[i - 1], s1[i - 1]);
sell[i] = Math.max(buy[i - 1], s1[i - 1]) + prices[i];
s2[i] = Math.max(s2[i - 1], sell[i - 1]);
}
return Math.max(sell[N - 1], s2[N - 1]);
}
需要交易费用的股票交易
- Best Time to Buy and Sell Stock with Transaction Fee (Medium)
Input: prices = [1, 3, 2, 8, 4, 9], fee = 2
Output: 8
Explanation: The maximum profit can be achieved by:
Buying at prices[0] = 1
Selling at prices[3] = 8
Buying at prices[4] = 4
Selling at prices[5] = 9
The total profit is ((8 - 1) - 2) + ((9 - 4) - 2) = 8.
题目描述：每交易一次，都要支付一定的费用。
public int maxProfit(int[] prices, int fee) {
int N = prices.length;
int[] buy = new int[N];
int[] s1 = new int[N];
int[] sell = new int[N];
int[] s2 = new int[N];
s1[0] = buy[0] = -prices[0];
sell[0] = s2[0] = 0;
for (int i = 1; i < N; i++) {
buy[i] = Math.max(sell[i - 1], s2[i - 1]) - prices[i];
s1[i] = Math.max(buy[i - 1], s1[i - 1]);
sell[i] = Math.max(buy[i - 1], s1[i - 1]) - fee + prices[i];
s2[i] = Math.max(s2[i - 1], sell[i - 1]);
}
return Math.max(sell[N - 1], s2[N - 1]);
}
class Solution {
public:
int maxProfit(vector<int>& prices, int fee) {
if (prices.size() <= 1) return 0;
vector<int> buy(prices.size()), sell(prices.size());
buy[0] = -prices[0] - fee;
for (int i = 1; i < prices.size(); i++) {
buy[i] = max(buy[i - 1], sell[i - 1] - prices[i] - fee);
sell[i] = max(sell[i - 1], buy[i - 1] + prices[i]);
}
return sell[prices.size() - 1];
}
};