K*****k
发帖数: 430 | 1 面经题：
Stock history data int stock[n], find the best sell and buy time.
化归题：
数组中，一个元素(第一个元素除外)减去它左边的某一个元素可以得到一个差值，求所
有这些差值的最大值。不是最大值减去最小值，比如：
{3, 4, 2, 7, 16, 1, 5, 11, 9}, 答案是16 - 2 = 14, 不是 16 - 1 = 15 | q****x
发帖数: 7404 | 2 just do max.
【在 K*****k 的大作中提到】
: 面经题：
: Stock history data int stock[n], find the best sell and buy time.
: 化归题：
: 数组中，一个元素(第一个元素除外)减去它左边的某一个元素可以得到一个差值，求所
: 有这些差值的最大值。不是最大值减去最小值，比如：
: {3, 4, 2, 7, 16, 1, 5, 11, 9}, 答案是16 - 2 = 14, 不是 16 - 1 = 15
| b*******y
发帖数: 232 | 3 如果是long position的话，两个题目是一样的
cracking google interview上面有解答
扫描一遍，maintain current min value以及maintain最大差值
【在 K*****k 的大作中提到】
: 面经题：
: Stock history data int stock[n], find the best sell and buy time.
: 化归题：
: 数组中，一个元素(第一个元素除外)减去它左边的某一个元素可以得到一个差值，求所
: 有这些差值的最大值。不是最大值减去最小值，比如：
: {3, 4, 2, 7, 16, 1, 5, 11, 9}, 答案是16 - 2 = 14, 不是 16 - 1 = 15
| K*****k
发帖数: 430 | 4 unsigned int MaxGain(int stock[], unsigned int N)
{
if (N < 2)
return 0;
int left_min = stock[0];
int max_gain = 0;
for (int i = 1; i < N; i++)
{
if (A[i] - left_min > max_gain)
max_gain = A[i] - left_min;
if (A[i] < left_min)
left_min = A[i];
}
return max_gain;
} | K*****k
发帖数: 430 | 5 面经作者的写法是否稍微繁琐了一点？(变量太多，行数还能再少一点)
虽然思路是一样的？
我总觉得白板代码应该以简洁为美。
=====================================================================
int maxgain =0, best_buytime = 0, best_selltime =0; current_buytime=0;
current_selltime =0;
for (i = 1 to stock.length - 1)
{
if (stock[i] > stock[current_selltime])
{
current_selltime = i ;
// update maxgain if possible
int current_gain = stock[current_selltime] - stock[current_buytime];
if(current_gain > maxgain)
{
maxgain = current_gain ;
best_selltime = current_selltime;
best_buytime = current_buytime;
}
}
if (stock[i] < stock[current_buytime])
{
current_selltime = i;
current_buytime = i;
}
}
【在 b*******y 的大作中提到】
: 如果是long position的话，两个题目是一样的
: cracking google interview上面有解答
: 扫描一遍，maintain current min value以及maintain最大差值
| m*****k
发帖数: 731 | 6 you only tracked maxgain, the original question wants sell and buy time. | m*****k
发帖数: 731 | 7 as my original post said, we can even compute the current local maxgain and
try to update global maxgain only when we get a new stock[i] < stock[current
_buyTime], this needs a dummy node at the end of stock[], otherwise we will
fail at [2, 3, 4, 5, 1, 2,3,4, 8] .
in this case [2, 3, 4, 5, 1, 2, 3 ,4, 8, -1(dummy node)],
we init with maxgain as 0, best_buy/best_sell as 0,
and current_buy/current_sell as 0,
then we move on starting from stock[1], only update current_sell again and
again since each stock[i] is greater than stock[current_sell], once we see
stock[i=4]==1 , 1 is smaller than stock[current_buy==0]==2, we know a new
local maxgain is coming, so we compute currently scanned local maxgain as
stock[current_sell]-stock[current_buy] = stock[3]-stock[0] = 5 -2 =3
and update global maxgain as 3, and remembers best_*,
then reset current_sell/current_buy to i=4,continue the loop, update current
_sell as we move along, when we reach -1, we compute local maxgain again and
get local maxgain as 8 - 1 =7, then update global maxgain again. | K*****k
发帖数: 430 | 8 如果要求buy time和sell time, 这样写就可以了么？
// Input: int stock[N]
// assert(N >= 2);
int min_index = 0;
int max_gain = 0;
int best_buytime = -1;
int best_selltime = -1;
for (int i = 1; i < N; i++)
{
if (stock[i] < stock[min_index])
min_index = i;
else if (stock[i] - stock[min_index] > max_gain)
{
max_gain = stock[i] - stock[min_index];
best_buytime = min_index;
best_selltime = i;
}
} |
|
