- iOS/Objective-C 元类和类别
- objective-c - -1001 错误,当 NSURLSession 通过 httpproxy 和/etc/hosts
- java - 使用网络类获取 url 地址
- ios - 推送通知中不播放声音
试图解决this : 假设您有一个数组,其中第 i 个元素是给定股票在第 i 天的价格。
设计一个算法来寻找最大利润。您最多可以完成两笔交易。
解决方法:我正在做的是一种分而治之的方法。
dp[i][j] 是第 ith</em> 天和 jth 天之间的最大利润。计算如下:
dp[i][j] = max(dp[i][j], max(价格[i] - 价格[j], dp[k][j], dp[i][k +1])),其中 k 小于 i 且大于 j。
现在我们只需要在下面找出两笔交易中的最大利润:
m = max(m, max(dp[i][j], dp[k][j] + dp[i][k+1]))
请给我提示以解决此问题,因为此处提供的现有解决方案已超时。
class Solution(object):
def profit(self, prices, dp):
m = 0
for w in range(1, len(prices)):
for i in range(1, len(prices)):
for j in range(i-w, i):
if i-w < 0:
continue
for k in range(j, i):
dp[i][j] = max(dp[i][j], max(prices[i] - prices[j], dp[k][j], dp[i][k+1]))
m = max(m, max(dp[i][j], dp[k][j] + dp[i][k+1]))
return m
def maxProfit(self, prices):
"""
:type prices: List[int]
:rtype: int
"""
dp = [[0 for i in range(len(prices)+1)] for i in range(len(prices)+1)]
return self.profit(prices, dp)
最佳答案
一个提示是对价格进行预处理,并找出以索引 i 结尾的价格出售可以获得的最大利润。然后,您可以从预处理向量的末尾开始找出问题的解决方案。这将解决使用 1-D DP 的问题,并且不会超时。
int maxProfit(vector<int>& prices) {
int mprof = 0;
if (prices.size()>1){
int maxprof = 0;
vector<int> mp; // max profit before each element
mp.push_back(0);
int st = *prices.begin();
for(int i = 1 ; i<=prices.size();i++){ //compute mp vector
if (mprof < prices[i]-st){mprof = prices[i]-st;}
if (prices[i]<st){st = prices[i];}
mp.push_back(mprof);
}
mprof = 0;
int ed = *(prices.end()-1);
for (int i = prices.size()-2; i>=0; i--){
if (mprof < ed - prices[i] + mp[i]) { mprof = ed - prices[i] + mp[i];}
if (prices[i]>ed) {ed = prices[i];}
}
}
return mprof;
}
关于python - 买卖股票动态规划的最佳时机,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/46641011/
我正在处理现有网站的移动版本,我无法解决菜单中链接的问题。 该问题仅发生在标准的 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
我是一名优秀的程序员,十分优秀!