121.Best Time to Buy and Sell Stock

Best Time to Buy and Sell Stock 家族目前来看有5道题,题目真的很好,让我看到了更大的世界。

题目链接

先从 III 开始,因为这个是hard,很有意思。

Best Time to Buy and Sell Stock III

题目

1
2
3
Say you have an array for which the $i^{th}$ 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.

给定一个Array,每天股票的价格,设计一个算法获得最大收益,最多只能交易2次。

分析

  • 根据股票的涨势,记住每一个涨势阶段(group) 的最小值(group_min),在涨势结束的时候,用最大的那个值,减去group_min,即可获得每个涨势的最多收益。

  • 上述分析如果不限制购买次数,是可以解决此问题的(比如 II 就可以这样解决),但是III限制值能最多交易2次,就会出现一个很有意思的问题。

比如 [1,2,4,2,5,7,2,4,9,0]中:
[1,2,4 | 2,5,7 | 2,4,9 | 0]
1->4 一个涨势,收益3
2->7 一个涨势,收益5
2->9 一个涨势,收益7

如果只是计算最大收益,3个加在一起即可,我合理的猜测,I 和 II 大概就是这个问题。

但是这里限制了次数2,我们会发现如果
[1,2,4,2,5,7 | 2,4,9 | 0]
1->7 与 2->9 收益更高一些,但是1->7又覆盖了1->4 2->7

如果后边的收益没有当前范围高的话,其实是没有必要替换的

到这里,这个问题一下子变得复杂起来了,看了一下题目的topic, array 和 dp

那估计得从dp角度来分析这个问题了。

第一个dp算法

每个位置的含义分别为:

states[][0]: one buy
states[][1]: one buy, one sell
states[][2]: two buys, one sell
states[][3]: two buy, two sells

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
int maxProfit(vector<int>& prices) {
int states[2][4] = { INT_MIN, 0, INT_MIN, 0 }; // 0: 1 buy, 1: one buy/sell, 2: 2 buys/1 sell, 3, 2 buys/sells
int len = prices.size(), i, cur = 0, next = 1;
for (i = 0; i<len; ++i)
{
states[next][0] = max(states[cur][0], -prices[i]);
states[next][1] = max(states[cur][1], states[cur][0] + prices[i]);
states[next][2] = max(states[cur][2], states[cur][1] - prices[i]);
states[next][3] = max(states[cur][3], states[cur][2] + prices[i]);
swap(next, cur);
}
return max(states[cur][1], states[cur][3]);
}
};

第二个dp算法

上一个算法中有 next 和 cur 交换的步骤,这其实是可以优化的。

基本是一回事…

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
int maxProfit(vector<int>& prices) {
int states[4] = { INT_MIN, 0, INT_MIN, 0 }; // 0: 1 buy, 1: one buy/sell, 2: 2 buys/1 sell, 3, 2 buys/sells
int len = prices.size(), i, cur = 0, next = 1;
for (i = 0; i<len; ++i)
{
states[3] = max(states[3], states[2] + prices[i]);
states[2] = max(states[2], states[1] - prices[i]);
states[1] = max(states[1], states[0] + prices[i]);
states[0] = max(states[0], -prices[i]);
}
return max(states[1], states[3]);
}
};

只能说这种动态规划,实在是洋气,同时存在4个状态转移方程,还一个依赖一个。

升级版 IV

IV 的问题比 III 要复杂,不过鉴于已经有了III的代码,可以模仿着写出来。

留意一下小陷阱,k可能比price长度要大,此时就没必要用动态规划了,用了反而容易超时。

准确的说,如果k的值比price的长度一半大,就没必要用了,毕竟 买卖 占用两个price坑。

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
37
38
39
class Solution {
public:
int maxProfit(int k, vector<int>& prices) {
if (k == 0)
return 0;
// 用不着动态规划
if (k > prices.size()) {
prices.push_back(0);
int group_min = prices[0], sum = 0;
for (int i = 1; i < prices.size(); i++) {
// 一个上升结束了
if (prices[i] < prices[i - 1]) {
sum += prices[i - 1] - group_min;
group_min = prices[i];
}
else {
group_min = min(group_min, prices[i]);
}
}
return sum;
}
vector<int> state(2 * k, 0);
for (int i = 0; i < k; i++) {
state[2*i] = INT_MIN;
}
for (int j = 0; j < prices.size(); j++) {
for (int i = 2 * k - 1; i >= 0; i--) {
// 表示正负
int flag = (i % 2) == 1 ? 1 : -1;
if (i == 0)
state[0] = max(state[0], -prices[j]);
else
state[i] = max(state[i], state[i - 1] + flag*prices[j]);
}
}
sort(state.begin(), state.end());
return state.back();
}
};

with Transaction Fee

只有两个状态:

  • s0 表示没有stock
  • s1 表示有 1 stock

s1 由s0状态下,花 p和手续费fee 获得
s0 由s1状态下,卖掉p获得

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
int maxProfit(vector<int>& prices, int fee) {
int s0 = 0, s1 = INT_MIN;
for (int p : prices) {
s1 = max(s1, s0 - p - fee);
s0 = max(s0, s1 + p);
}
return s0;
}
};

这种问题如果用常规方法做,很难。

121.Best Time to Buy and Sell Stock

https://iii.run/archives/3e4f5d2b23c1.html

作者

mmmwhy

发布于

2018-09-05

更新于

2021-05-30

许可协议