注：所有题目来源于https://leetcode-cn.com/
leetcode-121-买卖股票的最佳时机 难度：简单 题目：给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。 如果你最多只允许完成一笔交易（即买入和卖出一支股票一次），设计一个算法来计算你所能获取的最大 class Solution { public: int maxProfit(vector<int>& prices) { int n = prices.size(); if(n == 0) return 0; int res = 0; int minprice = INT_MAX; for(int i=0;i<n;i++) { if(prices[i] < minprice) minprice = prices[i]; if(prices[i]-minprice > res ) res = prices[i]-minprice; } return res; } }; leetcode-122-买卖股票的最佳时机2 难度：简单 题目：给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。 代码： class Solution { public: int maxProfit(vector<int>& prices) { int n = prices.size(); if(n < 2) return 0; int res = 0; for(int i=1;i<n;i++) { if(prices[i] > prices[i-1]) res += (prices[i]-prices[i-1]); } return res; } }; leetcode-123-买卖股票的最佳时机3 难度：困难 题目：给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。 代码： class Solution { public: int maxProfit(vector<int>& prices) { int n = prices.size(); if(n < 2) return 0; vector<vector<int> > dp(n,vector<int>(5,0)); dp[0][0] = 0; dp[0][1] = -prices[0]; dp[0][2] = 0; dp[0][3] = -prices[0]; dp[0][4] = 0; for(int i=1;i<n;i++) { dp[i][0] = 0; dp[i][1] = max(dp[i-1][1],dp[i-1][0]-prices[i] ); dp[i][2] = max(dp[i-1][2],dp[i-1][1]+prices[i] ); dp[i][3] = max(dp[i-1][3],dp[i-1][2]-prices[i] ); dp[i][4] = max(dp[i-1][4],dp[i-1][3]+prices[i] ); } return max(dp[n-1][2],dp[n-1][4]); } }; leetcode-188-买卖股票的最佳时机4 难度：困难 题目：给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。 代码：方法1：
class Solution { public: int maxProfit(int k, vector<int>& prices) { int n = prices.size(); if(n < 2) return 0; vector<vector<int> > dp(n,vector<int>(k*2+1,0)); dp[0][0] = 0; for(int i=1;i<k*2+1;i++)//奇数是买入，偶数是卖出 { if(i % 2 == 1) dp[0][i] = -prices[0]; if(i % 2 == 0) dp[0][i] = 0; } for(int i=1;i<n;i++) { dp[i][0] = 0; for(int j=1;j<k*2+1;j++) { if(j % 2 == 1) dp[i][j] = max(dp[i-1][j],dp[i-1][j-1]-prices[i] ); else dp[i][j] = max(dp[i-1][j],dp[i-1][j-1]+prices[i] ); } } int res = 0; for(int i=1;i<=k;i++) { res = max(dp[n-1][i*2],res ); } return res; } };方法1编译发现如果k很大，会有内存超时问题。 方法2：
class Solution { public: int maxProfit(int k, vector<int>& prices) { int n = prices.size(); if(n < 2) return 0; //判断是否存在无限次交易，我们认为k>=n/2为无限次交易 if(n/2 <= k) { int res = 0; for(int i=1;i<n;i++) { res += max(0,prices[i]-prices[i-1] ); } return res; } vector<vector<int> > dp(k+1,vector<int>(n,0)); for(int i=1;i<=k;i++) { int nMax = -prices[0]; for(int j=1;j<n;j++) { //假设第m天买入的股票，如果今天要卖，求m~j-1的最大利润,即nMax //nMax计算方法是：前一天买没买 nMax = max(nMax,dp[i-1][j-1]-prices[j-1] ); dp[i][j] = max(dp[i][j-1],nMax+prices[j] ); } } return dp[k][n-1]; } }; leetcode-309-最佳卖票股票时机含冷冻期 难度：中等 题目：给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格 。 设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）。卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。 代码： class Solution { public: int maxProfit(vector<int>& prices) { int n = prices.size(); if(n < 2) return 0; //三种状态，0持股、1冷冻期、2非冷冻期且未持股 //注意：这里的状态指的是今天结束后的状态 vector<vector<int> > dp(n,vector<int>(3,0)); dp[0][0] = -prices[0]; dp[0][1] = 0; dp[0][2] = 0; for(int i=1;i<n;i++) { dp[i][0] = max(dp[i-1][0],dp[i-1][2]-prices[i] ); dp[i][1] = dp[i-1][0]+prices[i]; dp[i][2] = max(dp[i-1][1],dp[i-1][2]); } int res = dp[n-1][1]; res = max(res,dp[n-1][2] ); return res; } }; leetcode-714-买卖股票的最佳时机含手续费 难度：中等 题目：给定一个整数数组 prices，其中第 i 个元素代表了第 i 天的股票价格 ；非负整数 fee 代表了交易股票的手续费用。 你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。返回获得利润的最大值。 注意：这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费。 代码： class Solution { //分两种情况：买或不买（卖或不动） public: int maxProfit(vector<int>& prices, int fee) { int n = prices.size(); if(n < 2) return 0; int buy = -prices[0]; int sell = 0; for(int i=1;i<n;i++) { buy = max(buy,sell-prices[i] ); sell = max(sell,buy+prices[i]-fee); } return sell; } };