- c - 在位数组中找到第一个零
- linux - Unix 显示有关匹配两种模式之一的文件的信息
- 正则表达式替换多个文件
- linux - 隐藏来自 xtrace 的命令
我花了大约 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;
}
我理解除了开头提到的两行之外的所有代码:
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] 是什么意思? for (j = 0; j < k; j ++) {
?我花了很多时间(3 小时)思考这个解决方案并将其与其他 DP 问题进行比较,但没有运气。我将它与最长递增子序列 DP 问题以及您应该如何“让长度 (k) 表示在位置 k 结束的最长递增子序列的长度”进行了比较,并尝试将该逻辑应用于此处的数组,但没有成功。
感谢您的帮助。
最佳答案
假设我们想将每个价格(或日期)视为买入日或卖出日,以得出最佳选择。 b
列表将每一天都视为buy
日,而s
列表将每一天视为sell
日。现在我们只是实现逻辑。可能有点令人困惑的是,因为 s
在 j + 1
更新,对于 s
列表,j
是前一天。
在 i
的价格的最佳 k
购买日是我们在 k
购买日已经拥有的价格,或者我们购买,这等于第 (k-1)
个最佳销售日(即令人困惑的 s[j]
)减去我们刚买入以来的买入价!
b[j] = _max(b[j], s[j] - prices[i]);
i
价格的最佳 k
卖出日是我们已经拥有的第 k
卖出日或最佳卖出日k
买入日(因为 k
交易既有买入也有卖出)加上今天的价格,因为我们刚刚卖出股票!
s[j + 1] = _max(s[j + 1], b[j] + prices[i]);
根据 OP 的要求,这里有一个例子:[5, 20, 15, 100, 35] k = 2
。
b represents the most profit at
the jth buy considering prices up to i:
max(b[j], s[j] - prices[i])
s represents the most profit at
the jth sell (index j+1 in s) considering prices up to i:
max(s[j + 1], b[j] + prices[i])
note that when j = 0, s[j] (the sell before the first buy)
is always 0
prices[0]:
j: 0 1
b: -5 -5 // max(-Inf, 0 - 5), max(-Inf, 0 - 5)
s: 0 0 // max(0, -5 + 5), max(0, -5 + 5)
prices[1]:
j: 0 1
b: -5 -5 // max(-5, 0 - 20), max(-5, 15 - 20)
s: 15 15 // max(0, -5 + 20), max(0, -5 + 20)
prices[2]:
j: 0 1
b: -5 0 // max(-5, 0 - 15), max(-5, 15 - 15)
s: 15 15 // max(15, -5 + 15), max(15, 0 + 15)
prices[3]:
j: 0 1
b: -5 0 // max(-5, 0 - 100), max(0, 0 - 100)
s: 95 100 // max(15, -5 + 100), max(15, 0 + 100)
prices[4]:
j: 0 1
b: -5 60 // max(-5, 0 - 35), max(0, 95 - 35)
s: 95 100 // max(95, -5 + 35), max(100, 60 + 35)
关于c - 这个买卖股票的递归DP算法的算法和底层结构是什么?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/57318811/
我正在处理现有网站的移动版本,我无法解决菜单中链接的问题。 该问题仅发生在标准的 android 浏览器上。在 Chrome、firefox、safari 甚至 IE 上,该网站都运行良好。该网站上的
几周来我一直在努力解决这个问题,但没有找到真正的解决方案。我发现了一种解决方法,但我觉得它很烦人。 图像在我的 Galaxy S3 的默认浏览器中加载模糊,但在 chrome 和 firefox 中它
安装了多个浏览器。我怎样才能打开http://www.google.com以编程方式使用内置(库存)浏览器? 最佳答案 使用内置浏览器,通常可以通过按菜单按钮使地址栏出现(当然是在按图标打开浏览器之后
我在面试中被问到这样的问题: 给定股票价格: MS | 500 Apl | 1000 Nefx| 500 MS | 500 每次新库存到来时,我们都必须添加到现有库存中,否则如果是新
我需要将每个键的值相乘,然后将所有值相加以打印一个数字。我知道这可能非常简单,但我被卡住了 在我看来,我会用类似的方式来解决这个问题: for v in prices: total = sum(v *
直到昨天这样的查询 http://autoc.finance.yahoo.com/autoc?query=a&callback=YAHOO.Finance.SymbolSuggest.ssCallba
我正在尝试找到一个在phonegap应用程序中绘制折线/股票图表的解决方案。我尝试过很多库:amcharts JS、highcharts,但没有一个能工作。 有人可以帮我完成这个任务吗?欢迎任何解决方
如果您在 Google 上查看股票(例如 search for 'Apple stocks' ),您会得到一个相当漂亮且交互式的图表,如下所示: 请注意垂直十字线和漂亮的工具提示。 事实证明,尝试在
首先,我必须说,我是人工智能方面的初学者。我遵循了大多数有关股市预测的教程,它们几乎都是相同的。这些教程使用一个数据集并分为两组。第一个是训练集,第二个是测试集。他们正在使用股票的收盘价来训练和制作模
最近在使用highchart stock(highstock.js)的时候遇到了一个很奇怪的问题。我加载了一些包含星期六数据点的数据点。当应用程序运行时,起初它看起来像这样: 没有图表出现,只有导航器
我已经在 Azure 中的存储帐户上部署了新的文件共享,自从我这样做以来,我不再能够执行 terraform 计划,而是收到以下错误: azurerm_storage_account_customer
我是一名优秀的程序员,十分优秀!