a*********e
发帖数: 18 | 1 好悲催啊。
面试是2m*2m的小房间，但却要挤下三个人（一个shadow）。
我一紧张然后就果断挂了第一面。（嗯，关于这个以前发过贴了）。
之后就是漫长的等结果啊。
都实习一年了，mentor、manager、还有4、5个eng给写了很好的feedback。
结果上周到了HC还是挂掉了。
还没给加面。竟然不给加面。。
还说觉得我的背景去做research比做software engineer更合适。
然后G的research又不招master的嘛。
刚收到拒信时各种shock啊，现在好多了。
感觉自己接受现实的速度有点太快了？呵呵～
顺便求大神们的各种内推啊（需要h1b sponsor）。
贴题了。昨天做leetcode时竟然发现在某个回复里有这道题：
http://www.leetcode.com/2010/11/best-time-to-buy-and-sell-stock
注意不是原题，而是下面的某回复：
www said on August 25, 2011 Reply
hey 1337coder,
i was given an interview question on this, but they had a following question
example, if it is 6,1,3,2,4,7, we can buy for 1 and sell for 3, and we can
buy for 2, and sell for 4,then buy on 4, sell for 7. total maxval =3-1+4-2+7
-4 = 7. They would like to have some O(n) solutions.
记得还有新的条件就是每次交易都有固定手续费c
一开始按着原题的思路走了，后来才想到用动归。
想复杂了，列了两个状态 largest_gain_with_stock_after_day[day], largest_gain_
without_stock_after_day[day].
然后才在提示下发现可以用largest_gain_after_day[day]来代替。
列了个O（n^2）的，开始优化，因为时间来不及了，随口说用堆可以O（nlogn），一出
门就后悔了，只要一个max的就可以了，所以应该是O（n）的。 |
C***U
发帖数: 2406 | 2 形势严峻啊 都实习了还能去不成
我们这样的机会更小了
【在 a*********e 的大作中提到】
: 好悲催啊。
: 面试是2m*2m的小房间，但却要挤下三个人（一个shadow）。
: 我一紧张然后就果断挂了第一面。（嗯，关于这个以前发过贴了）。
: 之后就是漫长的等结果啊。
: 都实习一年了，mentor、manager、还有4、5个eng给写了很好的feedback。
: 结果上周到了HC还是挂掉了。
: 还没给加面。竟然不给加面。。
: 还说觉得我的背景去做research比做software engineer更合适。
: 然后G的research又不招master的嘛。
: 刚收到拒信时各种shock啊，现在好多了。
|
a*********e
发帖数: 18 | 3 这倒不用担心，招的人还是相当之多的。我只是运气不好罢了。
【在 C***U 的大作中提到】
: 形势严峻啊 都实习了还能去不成
: 我们这样的机会更小了
|
h****n
发帖数: 1093 | 4 这个题在那个hack google interview电子书里有详细说明呵呵
下面回复的题倒是新的，研究一下
【在 a*********e 的大作中提到】
: 好悲催啊。
: 面试是2m*2m的小房间，但却要挤下三个人（一个shadow）。
: 我一紧张然后就果断挂了第一面。（嗯，关于这个以前发过贴了）。
: 之后就是漫长的等结果啊。
: 都实习一年了，mentor、manager、还有4、5个eng给写了很好的feedback。
: 结果上周到了HC还是挂掉了。
: 还没给加面。竟然不给加面。。
: 还说觉得我的背景去做research比做software engineer更合适。
: 然后G的research又不招master的嘛。
: 刚收到拒信时各种shock啊，现在好多了。
|
k***g
发帖数: 58 | 5 stock扩展那题题意不清啊，可以连续buy么？
比方说 2，1，5， 可以(buy2, sell 5)and (buy1, sell 5)么？这样gain是7。
这样的话 6,1,3,2,4,7,最大的gain也不是7了 |
h****n
发帖数: 1093 | 6 应该是要求sell之后才能buy
这题我怎么感觉把所有上升段累积起来即可 有什么trick么
★ Sent from iPhone App: iReader Mitbbs Lite 7.56 |
a*********e
发帖数: 18 | 7 每次买卖有手续费c的。
【在 h****n 的大作中提到】
: 应该是要求sell之后才能buy
: 这题我怎么感觉把所有上升段累积起来即可 有什么trick么
: ★ Sent from iPhone App: iReader Mitbbs Lite 7.56
|
f*****e
发帖数: 2992 | 8 用DP，O(n^2)
或者把所有谷底bottom b_i和谷峰peak p_j 按顺序排成一条直线，加上起点s,终点t,
然后
做一个acyclic graph。
0)s到b_i weight = 0
1)p_j和b_i到t的weight=0
2)b_i到所有p_j (j>i, p_j - b_i - C > 0)的weight= - (p_j - b_i - C)
3)p_j到所有b_i (i>j)的weight= 0
然后求起始点s到t的最短路径O(n^3)。
http://moodle.bracu.ac.bd/pluginfile.php/4784/mod_resource/cont
【在 a*********e 的大作中提到】
: 每次买卖有手续费c的。
|
h*****7
发帖数: 492 | 9 现在Google股价跌了好多啊，几天之内有10%，
会不会影响到招人呢？
【在 a*********e 的大作中提到】
: 这倒不用担心，招的人还是相当之多的。我只是运气不好罢了。
|
e***s
发帖数: 799 | 10 如果有固定手续费 3-1+4-2+7-4 = 7 不是最优解了，
应该是 3-1+7-2 = 7 因为这里只有两次交易 |
|
|
j******2
发帖数: 362 | 11 肯定是说在同等本金的情况下，赚钱最多。那么就应该买1卖5.
【在 k***g 的大作中提到】
: stock扩展那题题意不清啊，可以连续buy么？
: 比方说 2，1，5， 可以(buy2, sell 5)and (buy1, sell 5)么？这样gain是7。
: 这样的话 6,1,3,2,4,7,最大的gain也不是7了
|
C***U
发帖数: 2406 | 12 一个成熟的公司 不管股价咋样 是不会影响正常运行的吧
【在 h*****7 的大作中提到】
: 现在Google股价跌了好多啊，几天之内有10%，
: 会不会影响到招人呢？
|
e***s
发帖数: 799 | 13 CAIWU， 你什么时候的G onsite 啊？
【在 C***U 的大作中提到】
: 一个成熟的公司 不管股价咋样 是不会影响正常运行的吧
|
e***s
发帖数: 799 | 14 public static int GetMaxProfit(int[] Stock)
{
int buy = Stock.Length;
int sell = 0;
int ret = 0;
for (int i = 0; i < Stock.Length; i++)
{
// i == 0 && Stock[i + 1] > Stock[i], we need to buy at 0
if (i == 0)
{
if (Stock[i + 1] > Stock[i])
buy = i;
}
else
{
if (Stock[i - 1] > Stock[i])
{
if (i == Stock.Length - 1)
return ret;
buy = i;
}
// make sure you handle when i is the last index.
else if (i == Stock.Length - 1 || Stock[i + 1] < Stock[i
])
{
sell = i;
}
// make sure the profit get calculate buy before sell.
if (sell > buy)
ret += Stock[sell] - Stock[buy];
}
}
return ret;
}
O(n)。 |
d******i
发帖数: 76 | 15
谢谢您的解法，学习到了，不过有些小问题。
如果股票价格是{1, 1, 2, 3}
根据您的算法，貌似有些问题。
还有，如果只有一个元素的时候，也会有问题。
【在 e***s 的大作中提到】
: public static int GetMaxProfit(int[] Stock)
: {
: int buy = Stock.Length;
: int sell = 0;
: int ret = 0;
: for (int i = 0; i < Stock.Length; i++)
: {
: // i == 0 && Stock[i + 1] > Stock[i], we need to buy at 0
: if (i == 0)
: {
|
C***U
发帖数: 2406 | 16 我告诉他们几个日子 还没回复我
【在 e***s 的大作中提到】
: CAIWU， 你什么时候的G onsite 啊？
|
e***s
发帖数: 799 | 17 谢谢你，确实有BUG。改了一下，请指正
public static int GetMaxProfit(int[] Stock)
{
if (Stock.Length <= 1)
return 0;
int buy = Stock.Length;
int sell = 0;
int ret = 0;
for (int i = 0; i < Stock.Length; i++)
{
// first buy
if (buy == Stock.Length)
{
if(Stock[i] < Stock[i + 1])
buy = i;
}
else if (Stock[i - 1] > Stock[i])
{
if (i == Stock.Length - 1)
return ret;
buy = i;
}
// make sure you handle when i is the last index.
else if (i == Stock.Length - 1 || Stock[i + 1] < Stock[i])
{
sell = i;
}
// make sure the profit get calculate buy before sell.
if (sell > buy)
ret += Stock[sell] - Stock[buy];
}
return ret;
}
【在 d******i 的大作中提到】
:
: 谢谢您的解法，学习到了，不过有些小问题。
: 如果股票价格是{1, 1, 2, 3}
: 根据您的算法，貌似有些问题。
: 还有，如果只有一个元素的时候，也会有问题。
|
a*********e
发帖数: 18 | 18 注意哦，有固定手续费c的。
【在 e***s 的大作中提到】
: 谢谢你，确实有BUG。改了一下，请指正
: public static int GetMaxProfit(int[] Stock)
: {
: if (Stock.Length <= 1)
: return 0;
: int buy = Stock.Length;
: int sell = 0;
: int ret = 0;
: for (int i = 0; i < Stock.Length; i++)
: {
|
e***s
发帖数: 799 | 19 我的code已经尽量减少交易次数的，我觉得要看你的c是多少，如果1 买，2卖，还不够
交手续费的，那就另说了
【在 a*********e 的大作中提到】
: 注意哦，有固定手续费c的。
|
s********k
发帖数: 6180 | 20 贴个我的，如果一直再涨，就不用频繁交易,直到顶点为止,这个程序写成有交易费用的
也很容易，只需要再每次sell的时候判断
stocks[sell]-stocks[buy]>c
才进行交易
int getMaxProfit(int stocks [], int length){
int buy = 0;
int sell = 0;
int profit = 0;
bool hold = false;
for(int i = 0;i
int tmp = stocks[i];
if(stocks[i]
if(!hold){
buy = i;
hold = true;
}
if(hold&&(i==length-2)){
sell = i+1;
profit += stocks[sell]-stocks[buy];
hold = false;
}
}else if(stocks[i]>stocks[i+1]){
if(hold){
sell = i;
hold = false;
profit += stocks[sell]-stocks[buy];
}
}
}
return profit;
}
【在 j******2 的大作中提到】
: 肯定是说在同等本金的情况下，赚钱最多。那么就应该买1卖5.
|
|
|
e****e
发帖数: 418 | 21 I agree. Here is my code.
public static int beatStockMarketUnlimited(int[] prices) {
if ( prices == null || prices.length == 0 )
return 0;
int bestDeal = 0;
for ( int i = 0; i < prices.length - 1; i++ ) {
if ( prices[i] < prices[i+1] ) {
int startLow = i;
while ( i < prices.length - 1 && prices[i] < prices[i+1] )
i++;
int endHigh = i;
bestDeal += prices[endHigh] - prices[startLow];
}
}
return bestDeal;
}
【在 h****n 的大作中提到】
: 应该是要求sell之后才能buy
: 这题我怎么感觉把所有上升段累积起来即可 有什么trick么
: ★ Sent from iPhone App: iReader Mitbbs Lite 7.56
|
l*****i
发帖数: 136 | 22 greedy算法在固定费用上有问题，会陷入局部最优解
比如 1,2,3,5,4,7 c=3, 给出 5-1-3=1, 实际上是 7-1-3=3，看来还是得用dp
【在 s********k 的大作中提到】
: 贴个我的，如果一直再涨，就不用频繁交易,直到顶点为止,这个程序写成有交易费用的
: 也很容易，只需要再每次sell的时候判断
: stocks[sell]-stocks[buy]>c
: 才进行交易
: int getMaxProfit(int stocks [], int length){
: int buy = 0;
: int sell = 0;
: int profit = 0;
: bool hold = false;
: for(int i = 0;i
|
s********k
发帖数: 6180 | 23 确实，哪位给个DP的算法？
【在 l*****i 的大作中提到】
: greedy算法在固定费用上有问题，会陷入局部最优解
: 比如 1,2,3,5,4,7 c=3, 给出 5-1-3=1, 实际上是 7-1-3=3，看来还是得用dp
|
l*****i
发帖数: 136 | 24 想了很久，greedy可以，不过遇到peak之后不立即卖出，而是保存在为potentialSell,
然后check sliding down 的股价于potentialSell之间的gap是否大于cost fee. 大于
就讲potentialSell出手，否则继续观望是否有更好的sell point
【在 s********k 的大作中提到】
: 确实，哪位给个DP的算法？
|
g*****e
发帖数: 282 | 25 你设计的DP是说这样吧，gain[i]=max{gain[j]+price[i]-min{price[j+1~i]}} j=1~i-
1
这个没法简化到O(N)了。求教更简洁的DP设计=)
【在 a*********e 的大作中提到】
: 好悲催啊。
: 面试是2m*2m的小房间，但却要挤下三个人（一个shadow）。
: 我一紧张然后就果断挂了第一面。（嗯，关于这个以前发过贴了）。
: 之后就是漫长的等结果啊。
: 都实习一年了，mentor、manager、还有4、5个eng给写了很好的feedback。
: 结果上周到了HC还是挂掉了。
: 还没给加面。竟然不给加面。。
: 还说觉得我的背景去做research比做software engineer更合适。
: 然后G的research又不招master的嘛。
: 刚收到拒信时各种shock啊，现在好多了。
|
a*********e
发帖数: 18 | 26 好悲催啊。
面试是2m*2m的小房间，但却要挤下三个人（一个shadow）。
我一紧张然后就果断挂了第一面。（嗯，关于这个以前发过贴了）。
之后就是漫长的等结果啊。
都实习一年了，mentor、manager、还有4、5个eng给写了很好的feedback。
结果上周到了HC还是挂掉了。
还没给加面。竟然不给加面。。
还说觉得我的背景去做research比做software engineer更合适。
然后G的research又不招master的嘛。
刚收到拒信时各种shock啊，现在好多了。
感觉自己接受现实的速度有点太快了？呵呵～
顺便求大神们的各种内推啊（需要h1b sponsor）。
贴题了。昨天做leetcode时竟然发现在某个回复里有这道题：
http://www.leetcode.com/2010/11/best-time-to-buy-and-sell-stock
注意不是原题，而是下面的某回复：
www said on August 25, 2011 Reply
hey 1337coder,
i was given an interview question on this, but they had a following question
example, if it is 6,1,3,2,4,7, we can buy for 1 and sell for 3, and we can
buy for 2, and sell for 4,then buy on 4, sell for 7. total maxval =3-1+4-2+7
-4 = 7. They would like to have some O(n) solutions.
记得还有新的条件就是每次交易都有固定手续费c
一开始按着原题的思路走了，后来才想到用动归。
想复杂了，列了两个状态 largest_gain_with_stock_after_day[day], largest_gain_
without_stock_after_day[day].
然后才在提示下发现可以用largest_gain_after_day[day]来代替。
列了个O（n^2）的，开始优化，因为时间来不及了，随口说用堆可以O（nlogn），一出
门就后悔了，只要一个max的就可以了，所以应该是O（n）的。 |
C***U
发帖数: 2406 | 27 形势严峻啊 都实习了还能去不成
我们这样的机会更小了
【在 a*********e 的大作中提到】
: 好悲催啊。
: 面试是2m*2m的小房间，但却要挤下三个人（一个shadow）。
: 我一紧张然后就果断挂了第一面。（嗯，关于这个以前发过贴了）。
: 之后就是漫长的等结果啊。
: 都实习一年了，mentor、manager、还有4、5个eng给写了很好的feedback。
: 结果上周到了HC还是挂掉了。
: 还没给加面。竟然不给加面。。
: 还说觉得我的背景去做research比做software engineer更合适。
: 然后G的research又不招master的嘛。
: 刚收到拒信时各种shock啊，现在好多了。
|
a*********e
发帖数: 18 | 28 这倒不用担心，招的人还是相当之多的。我只是运气不好罢了。
【在 C***U 的大作中提到】
: 形势严峻啊 都实习了还能去不成
: 我们这样的机会更小了
|
h****n
发帖数: 1093 | 29 这个题在那个hack google interview电子书里有详细说明呵呵
下面回复的题倒是新的，研究一下
【在 a*********e 的大作中提到】
: 好悲催啊。
: 面试是2m*2m的小房间，但却要挤下三个人（一个shadow）。
: 我一紧张然后就果断挂了第一面。（嗯，关于这个以前发过贴了）。
: 之后就是漫长的等结果啊。
: 都实习一年了，mentor、manager、还有4、5个eng给写了很好的feedback。
: 结果上周到了HC还是挂掉了。
: 还没给加面。竟然不给加面。。
: 还说觉得我的背景去做research比做software engineer更合适。
: 然后G的research又不招master的嘛。
: 刚收到拒信时各种shock啊，现在好多了。
|
k***g
发帖数: 58 | 30 stock扩展那题题意不清啊，可以连续buy么？
比方说 2，1，5， 可以(buy2, sell 5)and (buy1, sell 5)么？这样gain是7。
这样的话 6,1,3,2,4,7,最大的gain也不是7了 |
|
|
h****n
发帖数: 1093 | 31 应该是要求sell之后才能buy
这题我怎么感觉把所有上升段累积起来即可 有什么trick么
★ Sent from iPhone App: iReader Mitbbs Lite 7.56 |
a*********e
发帖数: 18 | 32 每次买卖有手续费c的。
【在 h****n 的大作中提到】
: 应该是要求sell之后才能buy
: 这题我怎么感觉把所有上升段累积起来即可 有什么trick么
: ★ Sent from iPhone App: iReader Mitbbs Lite 7.56
|
f*****e
发帖数: 2992 | 33 用DP，O(n^2)
或者把所有谷底bottom b_i和谷峰peak p_j 按顺序排成一条直线，加上起点s,终点t,
然后
做一个acyclic graph。
0)s到b_i weight = 0
1)p_j和b_i到t的weight=0
2)b_i到所有p_j (j>i, p_j - b_i - C > 0)的weight= - (p_j - b_i - C)
3)p_j到所有b_i (i>j)的weight= 0
然后求起始点s到t的最短路径O(n^3)。
http://moodle.bracu.ac.bd/pluginfile.php/4784/mod_resource/cont
【在 a*********e 的大作中提到】
: 每次买卖有手续费c的。
|
h*****7
发帖数: 492 | 34 现在Google股价跌了好多啊，几天之内有10%，
会不会影响到招人呢？
【在 a*********e 的大作中提到】
: 这倒不用担心，招的人还是相当之多的。我只是运气不好罢了。
|
e***s
发帖数: 799 | 35 如果有固定手续费 3-1+4-2+7-4 = 7 不是最优解了，
应该是 3-1+7-2 = 7 因为这里只有两次交易 |
j******2
发帖数: 362 | 36 肯定是说在同等本金的情况下，赚钱最多。那么就应该买1卖5.
【在 k***g 的大作中提到】
: stock扩展那题题意不清啊，可以连续buy么？
: 比方说 2，1，5， 可以(buy2, sell 5)and (buy1, sell 5)么？这样gain是7。
: 这样的话 6,1,3,2,4,7,最大的gain也不是7了
|
C***U
发帖数: 2406 | 37 一个成熟的公司 不管股价咋样 是不会影响正常运行的吧
【在 h*****7 的大作中提到】
: 现在Google股价跌了好多啊，几天之内有10%，
: 会不会影响到招人呢？
|
e***s
发帖数: 799 | 38 CAIWU， 你什么时候的G onsite 啊？
【在 C***U 的大作中提到】
: 一个成熟的公司 不管股价咋样 是不会影响正常运行的吧
|
e***s
发帖数: 799 | 39 public static int GetMaxProfit(int[] Stock)
{
int buy = Stock.Length;
int sell = 0;
int ret = 0;
for (int i = 0; i < Stock.Length; i++)
{
// i == 0 && Stock[i + 1] > Stock[i], we need to buy at 0
if (i == 0)
{
if (Stock[i + 1] > Stock[i])
buy = i;
}
else
{
if (Stock[i - 1] > Stock[i])
{
if (i == Stock.Length - 1)
return ret;
buy = i;
}
// make sure you handle when i is the last index.
else if (i == Stock.Length - 1 || Stock[i + 1] < Stock[i
])
{
sell = i;
}
// make sure the profit get calculate buy before sell.
if (sell > buy)
ret += Stock[sell] - Stock[buy];
}
}
return ret;
}
O(n)。 |
d******i
发帖数: 76 | 40
谢谢您的解法，学习到了，不过有些小问题。
如果股票价格是{1, 1, 2, 3}
根据您的算法，貌似有些问题。
还有，如果只有一个元素的时候，也会有问题。
【在 e***s 的大作中提到】
: public static int GetMaxProfit(int[] Stock)
: {
: int buy = Stock.Length;
: int sell = 0;
: int ret = 0;
: for (int i = 0; i < Stock.Length; i++)
: {
: // i == 0 && Stock[i + 1] > Stock[i], we need to buy at 0
: if (i == 0)
: {
|
|
|
C***U
发帖数: 2406 | 41 我告诉他们几个日子 还没回复我
【在 e***s 的大作中提到】
: CAIWU， 你什么时候的G onsite 啊？
|
e***s
发帖数: 799 | 42 谢谢你，确实有BUG。改了一下，请指正
public static int GetMaxProfit(int[] Stock)
{
if (Stock.Length <= 1)
return 0;
int buy = Stock.Length;
int sell = 0;
int ret = 0;
for (int i = 0; i < Stock.Length; i++)
{
// first buy
if (buy == Stock.Length)
{
if(Stock[i] < Stock[i + 1])
buy = i;
}
else if (Stock[i - 1] > Stock[i])
{
if (i == Stock.Length - 1)
return ret;
buy = i;
}
// make sure you handle when i is the last index.
else if (i == Stock.Length - 1 || Stock[i + 1] < Stock[i])
{
sell = i;
}
// make sure the profit get calculate buy before sell.
if (sell > buy)
ret += Stock[sell] - Stock[buy];
}
return ret;
}
【在 d******i 的大作中提到】
:
: 谢谢您的解法，学习到了，不过有些小问题。
: 如果股票价格是{1, 1, 2, 3}
: 根据您的算法，貌似有些问题。
: 还有，如果只有一个元素的时候，也会有问题。
|
a*********e
发帖数: 18 | 43 注意哦，有固定手续费c的。
【在 e***s 的大作中提到】
: 谢谢你，确实有BUG。改了一下，请指正
: public static int GetMaxProfit(int[] Stock)
: {
: if (Stock.Length <= 1)
: return 0;
: int buy = Stock.Length;
: int sell = 0;
: int ret = 0;
: for (int i = 0; i < Stock.Length; i++)
: {
|
e***s
发帖数: 799 | 44 我的code已经尽量减少交易次数的，我觉得要看你的c是多少，如果1 买，2卖，还不够
交手续费的，那就另说了
【在 a*********e 的大作中提到】
: 注意哦，有固定手续费c的。
|
s********k
发帖数: 6180 | 45 贴个我的，如果一直再涨，就不用频繁交易,直到顶点为止,这个程序写成有交易费用的
也很容易，只需要再每次sell的时候判断
stocks[sell]-stocks[buy]>c
才进行交易
int getMaxProfit(int stocks [], int length){
int buy = 0;
int sell = 0;
int profit = 0;
bool hold = false;
for(int i = 0;i
int tmp = stocks[i];
if(stocks[i]
if(!hold){
buy = i;
hold = true;
}
if(hold&&(i==length-2)){
sell = i+1;
profit += stocks[sell]-stocks[buy];
hold = false;
}
}else if(stocks[i]>stocks[i+1]){
if(hold){
sell = i;
hold = false;
profit += stocks[sell]-stocks[buy];
}
}
}
return profit;
}
【在 j******2 的大作中提到】
: 肯定是说在同等本金的情况下，赚钱最多。那么就应该买1卖5.
|
e****e
发帖数: 418 | 46 I agree. Here is my code.
public static int beatStockMarketUnlimited(int[] prices) {
if ( prices == null || prices.length == 0 )
return 0;
int bestDeal = 0;
for ( int i = 0; i < prices.length - 1; i++ ) {
if ( prices[i] < prices[i+1] ) {
int startLow = i;
while ( i < prices.length - 1 && prices[i] < prices[i+1] )
i++;
int endHigh = i;
bestDeal += prices[endHigh] - prices[startLow];
}
}
return bestDeal;
}
【在 h****n 的大作中提到】
: 应该是要求sell之后才能buy
: 这题我怎么感觉把所有上升段累积起来即可 有什么trick么
: ★ Sent from iPhone App: iReader Mitbbs Lite 7.56
|
l*****i
发帖数: 136 | 47 greedy算法在固定费用上有问题，会陷入局部最优解
比如 1,2,3,5,4,7 c=3, 给出 5-1-3=1, 实际上是 7-1-3=3，看来还是得用dp
【在 s********k 的大作中提到】
: 贴个我的，如果一直再涨，就不用频繁交易,直到顶点为止,这个程序写成有交易费用的
: 也很容易，只需要再每次sell的时候判断
: stocks[sell]-stocks[buy]>c
: 才进行交易
: int getMaxProfit(int stocks [], int length){
: int buy = 0;
: int sell = 0;
: int profit = 0;
: bool hold = false;
: for(int i = 0;i
|
s********k
发帖数: 6180 | 48 确实，哪位给个DP的算法？
【在 l*****i 的大作中提到】
: greedy算法在固定费用上有问题，会陷入局部最优解
: 比如 1,2,3,5,4,7 c=3, 给出 5-1-3=1, 实际上是 7-1-3=3，看来还是得用dp
|
l*****i
发帖数: 136 | 49 想了很久，greedy可以，不过遇到peak之后不立即卖出，而是保存在为potentialSell,
然后check sliding down 的股价于potentialSell之间的gap是否大于cost fee. 大于
就讲potentialSell出手，否则继续观望是否有更好的sell point
【在 s********k 的大作中提到】
: 确实，哪位给个DP的算法？
|
g*****e
发帖数: 282 | 50 你设计的DP是说这样吧，gain[i]=max{gain[j]+price[i]-min{price[j+1~i]}} j=1~i-
1
这个没法简化到O(N)了。求教更简洁的DP设计=)
【在 a*********e 的大作中提到】
: 好悲催啊。
: 面试是2m*2m的小房间，但却要挤下三个人（一个shadow）。
: 我一紧张然后就果断挂了第一面。（嗯，关于这个以前发过贴了）。
: 之后就是漫长的等结果啊。
: 都实习一年了，mentor、manager、还有4、5个eng给写了很好的feedback。
: 结果上周到了HC还是挂掉了。
: 还没给加面。竟然不给加面。。
: 还说觉得我的背景去做research比做software engineer更合适。
: 然后G的research又不招master的嘛。
: 刚收到拒信时各种shock啊，现在好多了。
|
|
|
l**b
发帖数: 457 | |
