相同题目：剑指 Offer 63. 股票的最大利润
题目意思：只能买入一次，卖出一次，最大利润
- 思路二：贪心
时间复杂度：O(n)
空间复杂度：O(1)
class Solution {
public:
int maxProfit(vector& prices) {
int minPrice = INT_MAX;
int maxProfit = 0;
for (int price : prices) {
minPrice = min(minPrice, price); // 动态更新最小价格
maxProfit = max(maxProfit, price - minPrice);
}
return maxProfit;
}
};
思路三：动态规划
五部曲：
-
确定dp数组以及下标含义：
- dp[i][0]表示第i天交易完后手里没有股票的最大利润
- dp[i][1]表示第i天交易完后手里持有股票的最大利润
-
确定递推公式
- dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i]);
- dp[i][1] = max(dp[i-1][i], -prices[i]);
-
初始化
dp[i][0] = 0;
dp[i][1] = -prices[0];
时间复杂度：O(n)
空间复杂度：O(n)
class Solution { public: int maxProfit(vector& prices) { int n = prices.size(); int dp[n][2]; //初始化 dp[0][0] = 0; //第0天不持有股票的最大利润 dp[0][1] = -prices[0]; //第0天持有股票的最大利润 for (int i = 1; i < n; i++) { //第i天不持有股票的maxProfit = max(第i-1天不持有股票的maxProfit，第i-1天持有但第i天卖出时的maxProfit) dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i]); //第i天持有股票的maxProfit = max(第i-1天持有股票的maxProfit，今天刚买入股票时的maxProfit) dp[i][1] = max(dp[i-1][1], -prices[i]); } return dp[n-1][0]; } }; - 空间优化：
注意到上面的状态转移方程中，每一天的状态只与前一天的状态有关，而与更早的状态都无关，因此我们不必存储这些无关的状态，只需要将 dp[i-1][0]和 dp[i-1][1]存放在两个变量中，通过它们计算出 dp[i][0]和 dp[i][1]并存回对应的变量，以便于第 i+1天的状态转移即可。
空间复杂度：O(1)
class Solution { public: int maxProfit(vector& prices) { int n = prices.size(); int sell = 0; int buy = -prices[0]; for (int i = 1; i < n; ++i) { sell = max(sell, buy + prices[i]); buy = max(buy, -prices[i]); } return sell; } };
题目意思：
- 只有一只股票！
- 当前只有买股票或者买股票的操作
思路：把每一题的股价描点画成折线图，求所有上升线段的累加；借鉴376题
- 贪心：
时间复杂度：O(n)
空间复杂度：O(1)
class Solution {
public:
int maxProfit(vector& prices) {
int res = 0;
for(int i = 1; i < prices.size(); i++){
if(prices[i] - prices[i-1] > 0)
res += prices[i] - prices[i-1];
}
return res;
}
};
思路二：动态规划
时间复杂度：O(n)
空间复杂度：O(n)
五部曲：
-
确定dp数组以及下标含义：
- dp[i][0]表示第i天交易完后手里没有股票的最大利润
- dp[i][1]表示第i天交易完后手里持有股票的最大利润
-
确定递推公式
- dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i]);
- dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i]);
-
初始化
dp[i][0] = 0;
dp[i][1] = -prices[0];
class Solution {
public:
int maxProfit(vector& prices) {
int n = prices.size();
int dp[n][2];
dp[0][0] = 0;
dp[0][1] = -prices[0];
for(int i = 1; i < n; i++) {
dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i]);
dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i]);
}
return dp[n-1][0];
}
};
- 空间优化：
空间复杂度：O(1)
class Solution {
public:
int maxProfit(vector& prices) {
int n = prices.size();
int sell = 0;
int buy = -prices[0];
for (int i = 1; i < n; ++i) {
sell = max(sell, buy +prices[i]);
buy = max(buy, sell -prices[i]);
}
return sell;
}
};
- 思路：动态规划
时间复杂度：O(n)
空间复杂度：O(1)
看官方答案，能看懂
-
未进行过任何操作
-
只进行过一次买操作
-
进行了一次买操作和一次卖操作，即完成了一笔交易
-
在完成了一笔交易的前提下，进行了第二次买操作
-
完成了全部两笔交易
buy1：
- 在第i天不进行任何操作，保持原状态
- 在未进行任何操作的前提下以prices[i]的价格买入股票
buy1 = max(buy1, -prices[i]);
sell1：
- 在第i天不进行任何操作
- 在只进行过一次买操作的前提下，以prices[i]的价格卖出股票
sell1 = mamx(sell1, buy1+prices[i]);
class Solution {
public:
int maxProfit(vector& prices) {
//dp初始化
int buy1 = -prices[0];
int sell1 = 0;
int buy2 = -prices[0];
int sell2 = 0;
for(int i = 1; i < prices.size(); ++i){
//状态转移函数
buy1 = max(buy1, -prices[i]);
sell1 = max(sell1, buy1+prices[i]);
buy2 = max(buy2, sell1-prices[i]);
sell2 = max(sell2, buy2+prices[i]);
}
return sell2;
}
};
没进行空间优化之前是下面这样子：
-
没有操作
-
第一次买入
-
第一次卖出
-
第二次买入
-
第二次卖出
class Solution {
public:
int maxProfit(vector& prices) {
if (prices.size() == 0) return 0;
vector> dp(prices.size(), vector(5, 0));
dp[0][1] = -prices[0];
dp[0][3] = -prices[0];
for (int i = 1; i < prices.size(); i++) {
dp[i][0] = dp[i - 1][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 dp[prices.size() - 1][4];
}
};
方法：动态规划
-
确定dp下标以及含义：
- buy[i][j]：表示对于数组price[0~i]中的价格而言，恰好进行完j笔交易，并且当前手上持有一只股票，这时的最大利润
- sell[i][j]：表示恰好进行完j笔交易，并且当前手上不持有股票，这时的最大利润
-
确定状态转移函数
- buy[i][j] = max(buy[i-1][j], sell[i-1][j] - prices[i]);
- ``sell[i][j] = max(sell[i-1][j], buy[i-1][j-1] + prices[i]);`
-
dp初始化
buy[0][0] = -prices[0];
sell[0][0] = 0;
buy[0][1...k]是不合法的操作，设置一个不合理的值
sell[0][1...k]是不合法的操作
class Solution {
public:
int maxProfit(int k, vector& prices) {
if (prices.empty()) return 0;
int n = prices.size();
k = min(k, n / 2); //n天最多完成 n/2笔交易 这行相当于剪枝，不加也行
vector> buy(n, vector(k + 1));
vector> sell(n, vector(k + 1));
//初始化
buy[0][0] = -prices[0];
sell[0][0] = 0;
for (int i = 1; i <= k; ++i) {
buy[0][i] = sell[0][i] = INT_MIN / 2; //为什么除2，因为后面有+操作，就会超出int值
}
for (int i = 1; i < n; ++i) {
buy[i][0] = max(buy[i - 1][0], sell[i - 1][0] - prices[i]);
for (int j = 1; j <= k; ++j) {
buy[i][j] = max(buy[i - 1][j], sell[i - 1][j] - prices[i]);
sell[i][j] = max(sell[i - 1][j], buy[i - 1][j - 1] + prices[i]);
}
}
//为什么返回这个？ 最多完成k笔交易，但不是完成k笔交易时max
return *max_element(sell[n - 1].begin(), sell[n - 1].end());
}
};
空间优化：
class Solution {
public:
int maxProfit(int k, vector& prices) {
if (prices.empty()) return 0;
int n = prices.size();
k = min(k, n / 2);
vector buy(k + 1);
vector sell(k + 1);
buy[0] = -prices[0];
sell[0] = 0;
for (int i = 1; i <= k; ++i) {
buy[i] = sell[i] = INT_MIN / 2;
}
for (int i = 1; i < n; ++i) {
buy[0] = max(buy[0], sell[0] - prices[i]);
for (int j = 1; j <= k; ++j) {
buy[j] = max(buy[j], sell[j] - prices[i]);
sell[j] = max(sell[j], buy[j-1] + prices[i]);
}
}
return *max_element(sell.begin(), sell.end());
}
};
时间复杂度：O(n * min(n,k))
空间复杂度：O(min(n,k))
思路：动态规划
1、确定dp数组及其含义
- 目前持有一只股票，对应的累加最大收益记为f[i][0]
- 目前不持有任何股票，并给处于冷冻期中，对应的累计最大收益记为f[i][1]
- 目前不持有任何股票，并且不处于冷冻期中，对应的累计最大收益记为f[i][2]
2、确定状态转移函数
f[i][0] = max(f[i-1][0], f[i-1][2] - prices[i]);
f[i][1] = f[i-1][0] + prices[i];
f[i][2] = max(f[i-1][1], f[i-1][2]);
最终最大利润为：max(f[n-1][1], f[n-1][2])
3、初始化
f[0][0] = -prices[0];
f[0][1] = 0;
f[0][2] = 0;
时间复杂度：O(n)
空间复杂度：O(n)
class Solution {
public:
int maxProfit(vector& prices) {
if (prices.empty()) return 0;
int n = prices.size();
// f[i][0]: 手上持有股票的最大收益
// f[i][1]: 手上不持有股票，并且处于冷冻期中的累计最大收益
// f[i][2]: 手上不持有股票，并且不在冷冻期中的累计最大收益
vector> f(n, vector(3));
f[0][0] = -prices[0];
for (int i = 1; i < n; ++i) {
f[i][0] = max(f[i-1][0], f[i-1][2] - prices[i]);
f[i][1] = f[i-1][0] + prices[i];
f[i][2] = max(f[i-1][1], f[i-1][2]);
}
return max(f[n-1][1], f[n-1][2]);
}
};
空间优化：
空间复杂度：O(1)
class Solution {
public:
int maxProfit(vector& prices) {
if (prices.empty()) return 0;
int n = prices.size();
int f0 = -prices[0];
int f1 = 0;
int f2 = 0;
for (int i = 1; i < n; ++i) {
int newf0 = max(f0, f2 - prices[i]);
int newf1 = f0 + prices[i];
int newf2 = max(f1, f2);
f0 = newf0;
f1 = newf1;
f2 = newf2;
}
return max(f1, f2);
}
};
-
思路一：贪心
-
时间复杂度：O(n)
-
空间复杂度：O(1)
我们在做收获利润操作的时候其实有三种情况：
- 情况一：收获利润的这一天并不是收获利润区间里的最后一天（不是真正的卖出，相当于持有股票），所以后面要继续收获利润。
- 情况二：前一天是收获利润区间里的最后一天（相当于真正的卖出了），今天要重新记录最小价格了。
- 情况三：不作操作，保持原有状态（买入，卖出，不买不卖）
class Solution {
public:
int maxProfit(vector& prices, int fee) {
int res = 0;
int minPrice = prices[0]; // 记录最低价格
for (int i = 1; i < prices.size(); i++) {
// 情况二：相当于买入
if (prices[i] < minPrice) minPrice = prices[i];
// 情况三：保持原有状态（因为此时买则不便宜，卖则亏本）
//if (prices[i] >= minPrice && prices[i] <= minPrice + fee) {
// continue;
//}
// 计算利润，可能有多次计算利润，最后一次计算利润才是真正意义的卖出
if (prices[i] > minPrice + fee) {
res += prices[i] - minPrice - fee;
minPrice = prices[i] - fee; // 情况一，这一步很关键
}
}
return res;
}
};
当我们卖出一支股票时，我们就立即获得了以相同价格并且免除手续费买入一支股票的权利
- [x]
class Solution {
public:
int maxProfit(vector& prices, int fee) {
int buy = prices[0] + fee;
int profit = 0;
for (int i = 1; i < prices.size(); ++i) {
if (prices[i] + fee < buy) { //更新买入价
buy = prices[i] + fee;
}
else if (prices[i] > buy) { //收集利润
profit += prices[i] - buy;
buy = prices[i];
}
}
return profit;
}
};
思路二：动态规划
1、dp及其下标含义
dp[i][0]表示第i天交易完后手里没有股票的最大利润
dp[i][1]表示第i天交易完后手里持有一只股票的最大利润
2、转移函数
dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i] - fee);
dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i]);
3、初始化
dp[0][0] = 0;
dp[0][1] = -prices[0];
时间复杂度：O(n)
空间复杂度：O(n)
class Solution {
public:
int maxProfit(vector& prices, int fee) {
int n = prices.size();
vector> dp(n, vector(2));
//初始化
dp[0][0] = 0;
dp[0][1] = -prices[0];
for (int i = 1; i < n; ++i) {
dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i] - fee);
dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i]);
}
return dp[n-1][0];
}
};
空间优化
空间复杂度：O(1)
class Solution {
public:
int maxProfit(vector& prices, int fee) {
int n = prices.size();
//初始化
int sell = 0;
int buy = -prices[0];
//为什么从1开始，因为0已经初始化了
for (int i = 1; i < n; ++i) {
sell = max(sell, buy + prices[i] - fee);
buy = max(buy, sell - prices[i]);
}
return sell;
}
};
