LeetCode 六种买卖股票问题(C++)

1.买卖股票的最佳时机

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。

如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。

注意你不能在买入股票前卖出股票。

示例 1:

输入: [7,1,5,3,6,4] 输出: 5 解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。 注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。 示例 2:

输入: [7,6,4,3,1] 输出: 0 解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

思路

这种情况下只能买卖一次，考虑动态规划： buy[i]表示第i天买入的最大收益； sell[i]表示第i天卖出的最大收益； 则有：前i天的最大收益 = max{前i-1天的最大收益，第i天的价格-前i-1天中的最小价格} buy[i] = max(buy[i-1], - price[i]); 买入更低价格的股或不操作 sell[i] = max(sell[i-1], buy[i-1] + price[i])；即卖出或者不操作 优化存储空间后得到： sell = max(sell, buy + price[i])； buy = max(buy, - price[i])；

代码

class Solution { public: int maxProfit(vector<int>& prices) { int buy=INT_MIN,sell=0; for(int price : prices) { sell=max(sell,buy+price); buy=max(buy,-price); } return sell; } };

2.买卖股票的最佳时机 II

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1:

输入: [7,1,5,3,6,4] 输出: 7 解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。 随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。

思路

这种情况下可以多次买卖股票，有两种思路： 1、第一种算法是可以直接简化为只要今天比昨天大，就卖出。 2、第二种是画出状态转移框架，使用动态规划得出递归方程。 buy[i]代表当天买入的最大收益，sell[i]代表当天卖出的最大收益。 根据状态转换图可以得到： buy[i] = max(buy[i-1],sell[i-1] - price[i]); 即买入或者不操作 sell[i] = max(sell[i-1], buy[i-1] + price[i])；即卖出或者不操作 优化存储空间后得到： int pre_buy=buy; buy = max(buy,sell - price[i])； sell = max(sell, pre_buy + price[i])；

代码

class Solution { public: int maxProfit(vector<int>& prices) { int buy=INT_MIN,sell=0; for(int price : prices) { int pre_buy=buy; buy=max(buy,sell-price); sell=max(sell,pre_buy+price); } return sell; } /* int maxProfit(vector<int>& prices) {//算法可以直接简化为只要今天比昨天大，就卖出 if(prices.size()<=1) return 0; int ans=0; for(int i=0;i<prices.size()-1;i++) { int tmp=prices[i+1]-prices[i]; if(tmp>0) ans+=tmp; } return ans; } */ };

3.买卖股票的最佳时机 III

给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。

注意: 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1:

输入: [3,3,5,0,0,3,1,4] 输出: 6 解释: 在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3 。 随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天 （股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3 。

思路

这种情况下只能买卖两次，考虑动态规划递归： s1[i]表示第i天第一次买入的最大收益； s2[i]表示第i天第一次卖出的最大收益； s1[i]表示第i天第二次买入的最大收益； s2[i]表示第i天第二次卖出的最大收益； 则有： s1[i] = max(s1[i-1], - price[i]); 第一次买入更低价格的股或者不操作 s2[i] = max(s2[i-1], s1[i-1] + price[i])；即第一次卖出或者不操作 s3[i] = max(s3[i-1], s2[i-1] - price[i]); 第二次买入或者不操作 s4[i] = max(s4[i-1], s3[i-1] + price[i])；即第二次卖出或者不操作 优化存储空间后得到： s4=max(s4,s3+price); s3=max(s3,s2-price); s2=max(s2,s1+price); s1=max(s1,-price);

代码

class Solution { public: int maxProfit(vector<int>& prices) { if(prices.size()<=0) return 0; int s1=INT_MIN,s2=0,s3=INT_MIN,s4=0; for(int price : prices) { s4=max(s4,s3+price); s3=max(s3,s2-price); s2=max(s2,s1+price); s1=max(s1,-price); } return s4; } };

4.买卖股票的最佳时机 IV

给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。

注意: 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1:

输入: [2,4,1], k = 2 输出: 2 解释: 在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2 。

思路

这种情况下能买卖k次： 1、当k大于等于数组长度一半时, 问题就转换为了任意交易次数,此时采用买卖股票的最佳时机II,这里说是长度的一半是因为，每一笔交易都不能相互重叠 2、对于其他的k, 问题IV是对问题III的推广,在III中定义了两组买入和卖出时最大收益的变量, 在这里就是k组这样的变量

代码

class Solution { public: int maxProfit(int k, vector<int>& prices) { if(prices.size()<=0 || k==0) return 0; //当k大于等于数组长度一半时, 问题就转换为了任意交易次数,此时采用买卖股票的最佳时机II,这里说是长度的一半是因为，每一笔交易都不能相互重叠 if(2*k>=prices.size()) return maxProfitII(prices); //对于其他的k, 问题IV是对问题III的推广,在III中定义了两组买入和卖出时最大收益的变量, 在这里就是k组这样的变量 vector<int> buy(k,INT_MIN); vector<int> sell(k,0); for(int i=0;i<prices.size();i++) { for(int j=k-1;j>=1;j--) { sell[j]=max(sell[j],buy[j]+prices[i]);//第j次卖出的最高收益为要么不操作要么在第j次买入后卖出 buy[j]=max(buy[j],sell[j-1]-prices[i]);//第j次买入的最高收益为要么不操作要么在第j-1次卖出后买入 } sell[0]=max(sell[0],buy[0]+prices[i]); buy[0]=max(buy[0],-prices[i]); } return sell[k-1]; } int maxProfitII(vector<int>& prices) { int res=0; for(int i=1;i<prices.size();i++) { int tmp=prices[i]-prices[i-1]; if(tmp>0) res+=tmp; } return res; } };

5.最佳买卖股票时机含冷冻期

给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格 。​

设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:

你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。 卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。 示例:

输入: [1,2,3,0,2] 输出: 3 解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]

思路

这种情况同样考虑状态转移图得到动态规划递归方程： buy[i] = max(buy[i-1], cool[i-1] - price[i]) sell[i] = buy[i-1] + price[i]; cool[i] = max(cool[i-1], sell[i-1]) 优化存储空间后得到： int pre_sell=sell; sell=buy+price[i]; buy=max(buy,cool-price[i]); cool=max(cool,pre_sell);

代码

class Solution { public: int maxProfit(vector<int>& prices) { int buy=INT_MIN,sell=0,cool=0; for(int price : prices) { int pre_sell=sell; sell=buy+price; buy=max(buy,cool-price); cool=max(cool,pre_sell); } return max(sell,cool); } };

6.买卖股票的最佳时机含手续费

给定一个整数数组 prices，其中第 i 个元素代表了第 i 天的股票价格 ；非负整数 fee 代表了交易股票的手续费用。

你可以无限次地完成交易，但是你每次交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。

返回获得利润的最大值。

示例 1:

输入: prices = [1, 3, 2, 8, 4, 9], fee = 2 输出: 8 解释: 能够达到的最大利润: 在此处买入 prices[0] = 1 在此处卖出 prices[3] = 8 在此处买入 prices[4] = 4 在此处卖出 prices[5] = 9 总利润: ((8 - 1) - 2) + ((9 - 4) - 2) = 8.

思路

这种情况只需在第二种情况下作如下改动：这里fee当然也可以放在sell里减，但是放到buy里减掉，相当于买入时需要付多余的价格，这样可以处理int型整数溢出的问题。 sell = max(sell, buy + price[i])； buy = max(buy,sell - price[i] - fee)；

代码

class Solution { public: int maxProfit(vector<int>& prices, int fee) {//动态规划，buy表示当天买入股票的最大收益，sell表示当天卖出股票的最大收益 int buy=INT_MIN,sell=0; for(int price : prices) { sell=max(sell,buy+price); buy=max(buy,sell-price-fee); } return sell; } };