题目
Say you have an array for which the ith element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete at most two transactions.
Note: You may not engage in multiple transactions at the same time (i.e., you must sell the stock before you buy again).
Example 1:
Input: [3,3,5,0,0,3,1,4] Output: 6 Explanation: Buy on day 4 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3. Then buy on day 7 (price = 1) and sell on day 8 (price = 4), profit = 4-1 = 3.
Example 2:
Input: [1,2,3,4,5] Output: 4 Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4. Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are engaging multiple transactions at the same time. You must sell before buying again.
Example 3:
Input: [7,6,4,3,1] Output: 0 Explanation: In this case, no transaction is done, i.e. max profit = 0.
题解
- 本题题目意思比较简单，给出连续n天交易日的股票价格，问在其中什么时候买入什么时候卖出获得最大的收入，求出最大的收入值是多少。本题还有一点是比较关键的，最多允许两次交易，并且交易日期中买入股票和卖出股票不能在同一天。
解法 1 - 超时
以某个交易日为分界线将总时间分成两个时间段，计算该天前包括当天的交易获利以及该天以后时间段的交易获利，最后计算总和获得交易两次的最大获利
- 时间复杂度 - $O(n^2)$
- 空间复杂度 - $O(n)$
实现代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36// 解法1
class Solution {
public:
int maxProfit(vector<int>& prices) {
if(prices.size() <= 1) return 0;
int pre[prices.size()] = {0};
int post[prices.size()] = {0};
// 求某天前(包括当天)成交的最大利润
int prebase = prices[0];
int preMaxProfit = 0;
for(int i = 1; i < prices.size(); ++i) {
preMaxProfit = max(preMaxProfit, prices[i] - prebase);
pre[i] = preMaxProfit;
prebase = min(prebase, prices[i]);
}
// 求某天后成交的最大利润
int postBase = prices[prices.size() - 1];
int postMaxProfit = 0;
for(int i = prices.size() - 1; i >= 1; --i) {
postMaxProfit = max(postMaxProfit, postBase - prices[i]);
post[i-1] = postMaxProfit;
postBase = max(postBase, prices[i]);
}
int maxProfit = 0;
for(int i = 0; i < prices.size(); ++i)
for(int j = 0; j < prices.size(); ++j)
maxProfit = max(maxProfit, pre[i] + post[i]);
return maxProfit;
}
};- 结果 -
超时
解法 2
该解法其实是总结了一下
解法 1以及参考了一下评论里面的解法，其实现起来也比较简单，但是理解起来稍微费解一点，其维护四个变量，buy1表示第一次买股票的花费，sell1表示第一次交易股票后获得的利润，buy2表示第二次买股票后剩余的钱（第一次交易利润-购买的股票价格），sell2表示第二次交易后剩余的钱，即两次交易下来最后的盈利。当然也不一定需要两次交易，加入交易以后亏钱的话是不会进行交易的。- 时间复杂度 - $O(n)$
- 空间复杂度 - $O(1)$
实现代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19// 解法2
class Solution {
public:
int maxProfit(vector<int>& prices) {
if(prices.size() <= 1) return 0;
int buy1 = INT_MIN, buy2 = INT_MIN;
int sell1 = 0, sell2 = 0;
for(int price : prices){
buy1 = max(buy1, -price);
sell1 = max(sell1, buy1 + price);
buy2 = max(buy2, sell1 - price);
sell2 = max(sell2, buy2 + price);
}
return sell2;
}
};
解法 3
- 这个解法与解法 2的思路类似，但是做了一定的拓展，其不仅仅适用于只交易2次，也可以拓展适用于交易
k次的情况。对于profit[i][j]即交易日i到交易日j这个时间段买入的收入，其应该是大于等于profit[i][j-1]，即大于前一个时间都的利润，同时其也可以在第j个交易日卖出自己的股票，此时收益为余额 + 卖出价格，此时当前时间段最大利润值为余额 + 卖出价格与profit[i][j-1]的最大值 - 实现代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26// 解法3
class Solution {
public:
int maxProfit(vector<int>& prices) {
if(prices.size() <= 1) return 0;
// 交易两次，得到的利润
int profit[3][prices.size()];
// init
for(int i = 0; i < 3; ++i)
for(int j = 0; j < prices.size(); ++j)
profit[i][j] = 0;
for(int i = 1; i <= 2; ++i) {
int balance = -prices[0];
for(int j = 1; j < prices.size(); j++) {
profit[i][j] = max(profit[i][j - 1], balance + prices[j]);
balance = max(balance, profit[i - 1][j - 1] - prices[j]);
}
}
return profit[2][prices.size()-1];
}
};