我花了大约3个小时来理解这段代码,但我无法理解其中两行:
b[j] = _max(b[j], s[j] - prices[i]);
s[j + 1] = _max(s[j + 1], b[j] + prices[i]);
以下代码是针对以下问题的DP解决方案: 股票买卖的最佳时机
假设你有一个数组,其中第i个元素是第i天给定股票的价格。
设计一种算法来找到最大利润。您可以完成至多k次交易。
注意: 您不能同时进行多个交易(即在再次购买之前必须出售股票)。
示例1: 输入:[2,4,1],k = 2 输出:2 解释:在第1天买入(价格=2),在第2天卖出(价格=4),利润=4-2=2。
示例2: 输入:[3,2,6,5,0,3],k = 2 输出:7 解释:在第2天买入(价格=2),在第3天卖出(价格=6),利润=6-2=4。 然后在第5天买入(价格=0),在第6天卖出(价格=3),利润=3-0=3。
int _max(int a, int b) {
return a > b ? a : b;
}
int all_profits(int* prices, int pricesSize) {
int i, d, p;
p = 0;
for (i = 1; i < pricesSize; i ++) {
d = prices[i] - prices[i - 1];
p = d > 0 ? p + d : p; // get it as long as it is a profit!
}
return p;
}
int maxProfit(int k, int* prices, int pricesSize) {
int *b, *s, *buff, i, j, p;
if (pricesSize < 2) return 0;
if (k >= pricesSize / 2) return all_profits(prices, pricesSize);
buff = malloc((2 * k + 1) * sizeof(int));
//assert(buff);
b = &buff[0];
s = &buff[k];
for (i = 0; i < k; i ++) {
b[i] = 0x80000000; // min integer
s[i] = 0;
}
s[k] = 0;
for (i = 0; i < pricesSize; i ++) {
for (j = 0; j < k; j ++) {
// profit on buy is current buy or last sale minus today's price
b[j] = _max(b[j], s[j] - prices[i]);
// profit on sale is current sale or last buy plus today's price
s[j + 1] = _max(s[j + 1], b[j] + prices[i]);
}
}
p = s[k];
free(buff);
return p;
}
我理解代码的全部内容,除了开头提到的两行代码:
- buff数组的目的是什么?buff数组分为两部分,一部分包含b,另一部分包含s。据我所知,s[n]是您可以在第n天实现的最大利润。我不知道b在做什么。
- 为什么我们要做MAX of
b[j] = _max(b[j], s[j] - prices[i]);
,购买价格不应该是最低的吗?为什么b[j]是这两个数的最大值?s[j] - prices[i]是什么意思? - 这可能也与算法有关,但为什么会有这个语句:
s[j + 1] = _max(s[j + 1], b[j] + prices[i]);
这个表达式中的b[j] + prices[i]是干什么的,它的含义是什么? - 为什么我们要经过每天k次循环:
for (j = 0; j < k; j ++) {
?
我花费了很多时间(3小时)思考这个解决方案并将其与其他DP问题进行比较,但没有成功。我将其与最长递增子序列DP问题进行比较,并尝试将该逻辑应用于这里的数组,但没有成功。
感谢您的任何帮助。
k
,比如2,你可能想自己写出表格。按照更新逻辑,将每个价格视为每个交易的买入或卖出(显然有一些限制,因为第一个价格不能是卖出或第二次交易等。这些可以通过在表格中引用常量来轻松处理)。 - גלעד ברקןj
正在追踪k
,因此在表格中不需要k
。只需观察每个价格(i
)重新访问j
时如何再次更新s
和b
。j
是第k
次买入或卖出(第1次买入/卖出,第2次买入/卖出等)。 - גלעד ברקןs
和b
列表来观察所使用的有限空间。 - גלעד ברקן