h****n
发帖数: 1093 | 1 Best Time to Buy and Sell Stock II
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 as many
transactions as you like (ie, buy one and sell one share of the stock
multiple times). However, you may not engage in multiple transactions at the
same time (ie, you must sell the stock before you buy again).
Leetcode上这个题是不是有问题。。
我把上升段加一起就可以通过全部的test cases
难道题就这么简单？
class Solution {
public:
int maxProfit(vector &prices) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int size = prices.size();
int i;
int maxPro = 0;
if(size<1) return 0;
for(i=1;i
{
if(prices[i]>=prices[i-1])
{
maxPro += prices[i]-prices[i-1];
}
}
return maxPro;
}
}; |
h****n
发帖数: 1093 | 2 Best Time to Buy and Sell Stock II
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 as many
transactions as you like (ie, buy one and sell one share of the stock
multiple times). However, you may not engage in multiple transactions at the
same time (ie, you must sell the stock before you buy again).
Leetcode上这个题是不是有问题。。
我把上升段加一起就可以通过全部的test cases
难道题就这么简单？
class Solution {
public:
int maxProfit(vector &prices) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int size = prices.size();
int i;
int maxPro = 0;
if(size<1) return 0;
for(i=1;i
{
if(prices[i]>=prices[i-1])
{
maxPro += prices[i]-prices[i-1];
}
}
return maxPro;
}
}; |
N*********6
发帖数: 4372 | 3 估计对于这个道题应该可以，记得有网友说过如果每个transaction有
手续费c的话，可能要稍微再加点东西
the
【在 h****n 的大作中提到】
: Best Time to Buy and Sell Stock II
: 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 as many
: transactions as you like (ie, buy one and sell one share of the stock
: multiple times). However, you may not engage in multiple transactions at the
: same time (ie, you must sell the stock before you buy again).
: Leetcode上这个题是不是有问题。。
: 我把上升段加一起就可以通过全部的test cases
: 难道题就这么简单？
|
h****n
发帖数: 1093 | 4 我是觉得oj应该把这个换成那个手续费的 毕竟目前这个简单的弄花时间弄那么多test
cases不太值得
估计对于这个道题应该可以，记得有网友说过如果每个transaction有手续费c的话，可
能要稍微再加点东西
★ Sent from iPhone App: iReader Mitbbs Lite 7.56
【在 N*********6 的大作中提到】
: 估计对于这个道题应该可以，记得有网友说过如果每个transaction有
: 手续费c的话，可能要稍微再加点东西
:
: the
|
C***U
发帖数: 2406 | 5 恩 没有手续费确实是这样的
the
【在 h****n 的大作中提到】
: Best Time to Buy and Sell Stock II
: 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 as many
: transactions as you like (ie, buy one and sell one share of the stock
: multiple times). However, you may not engage in multiple transactions at the
: same time (ie, you must sell the stock before you buy again).
: Leetcode上这个题是不是有问题。。
: 我把上升段加一起就可以通过全部的test cases
: 难道题就这么简单？
|
k***g
发帖数: 58 | 6 有cost的话，难道不是每个上升阶段大于cost就交易，不是的话就不交易么？
Any counter example? |
h****n
发帖数: 1093 | 7 比如每次交易cost是1
1 2 3 按照你的解法就是每次都不能交易 最后的profit也是0
但是最大profit应该是1买入，之后等到3卖出，这样子也有profit 2-1 = 1
【在 k***g 的大作中提到】
: 有cost的话，难道不是每个上升阶段大于cost就交易，不是的话就不交易么？
: Any counter example?
|
g*****e
发帖数: 282 | 8 每个上升阶段的最大差大于交易费用就买入好了
【在 h****n 的大作中提到】
: 比如每次交易cost是1
: 1 2 3 按照你的解法就是每次都不能交易 最后的profit也是0
: 但是最大profit应该是1买入，之后等到3卖出，这样子也有profit 2-1 = 1
|
h****n
发帖数: 1093 | 9 试试1 3 2 4 cost为2的情况 你说的就没法交易 但实际上1 买入4卖出即可盈利1块
每个上升阶段的最大差大于交易费用就买入好了
★ Sent from iPhone App: iReader Mitbbs Lite 7.56
【在 g*****e 的大作中提到】
: 每个上升阶段的最大差大于交易费用就买入好了
|
l****o
发帖数: 315 | 10 LZ解法好简单。。。刚才写了个找买卖点的。刚好可解手续费。 |
|
|
h****n
发帖数: 1093 | 11 说说思路呗
【在 l****o 的大作中提到】
: LZ解法好简单。。。刚才写了个找买卖点的。刚好可解手续费。
|
l****o
发帖数: 315 | 12 就是每次的更新buy点都会在prices[i] < prices[i - 1]上。 如果prices[i - 1] -
buy >transcation cost就把差价加上去，然后更新下一个买入价buy = prices[i]。
然后处理一些特殊情况，比如全部或剩下的prices递增递减，然后到最后一个股票怎么
处理。
这样可行否。
【在 h****n 的大作中提到】
: 说说思路呗
|
h****n
发帖数: 1093 | 13 不行的你看看我上面举的反例
就是每次的更新buy点都会在prices[i]
★ Sent from iPhone App: iReader Mitbbs Lite 7.56
【在 l****o 的大作中提到】
: 就是每次的更新buy点都会在prices[i] < prices[i - 1]上。 如果prices[i - 1] -
: buy >transcation cost就把差价加上去，然后更新下一个买入价buy = prices[i]。
: 然后处理一些特殊情况，比如全部或剩下的prices递增递减，然后到最后一个股票怎么
: 处理。
: 这样可行否。
|
l****o
发帖数: 315 | 14 对。不行。哎。O(n)的暂时想不出。
【在 h****n 的大作中提到】
: 不行的你看看我上面举的反例
:
: 就是每次的更新buy点都会在prices[i]
: ★ Sent from iPhone App: iReader Mitbbs Lite 7.56
|
p****c
发帖数: 35 | 15 Is the leetcode answer correct?
In the "judge large", the given answer to [1, 2, 4, 7] is 6. However, if I
buy at 1 and 2, then sell at 4 and 7, my profit will be (4 - 1) + (7 - 2) =
8. Am I missing anything?
Thanks. |
C***U
发帖数: 2406 | 16 O(n)用dp吧
=
【在 p****c 的大作中提到】
: Is the leetcode answer correct?
: In the "judge large", the given answer to [1, 2, 4, 7] is 6. However, if I
: buy at 1 and 2, then sell at 4 and 7, my profit will be (4 - 1) + (7 - 2) =
: 8. Am I missing anything?
: Thanks.
|
c********t
发帖数: 5706 | 17 好像如果买了，必须先卖掉，才能再买。答案是 buy 1, sell 4 then buy 4, sell 7,
profit=6。我唯一的意见是，哪个操盘手会sell 4 then buy 4?
=
【在 p****c 的大作中提到】
: Is the leetcode answer correct?
: In the "judge large", the given answer to [1, 2, 4, 7] is 6. However, if I
: buy at 1 and 2, then sell at 4 and 7, my profit will be (4 - 1) + (7 - 2) =
: 8. Am I missing anything?
: Thanks.
|
l****o
发帖数: 315 | 18 怎么d。求细节。
【在 C***U 的大作中提到】
: O(n)用dp吧
:
: =
|
p****c
发帖数: 35 | 19 OK. Got it. The solution makes sense then. Although the problem doesn't
really :-)
7,
【在 c********t 的大作中提到】
: 好像如果买了，必须先卖掉，才能再买。答案是 buy 1, sell 4 then buy 4, sell 7,
: profit=6。我唯一的意见是，哪个操盘手会sell 4 then buy 4?
:
: =
|
