解答一下google intern 那两个算法题

你这是因果倒置。数学归纳法来源于递归思想，你说的一半算法也来源于递归思想。递归是源头，数学归纳法只是一种利用到递归的证明手段而已。
Jawley 发表于 2011-2-7 06:43

其实无所谓鸡生蛋，蛋生鸡了。我可以用数学归纳法证明递归的解法，递归的解法也可以从数学归纳法思考出来。

19# Jawley

Q2:记录波峰波谷到一个数组： 比如1，-1，3，4，-2，3,0....
f(1)读到第一个上升区间为止，比如1,-1,3 : 记录最低点-1,最大差3-（-1） = 4
f(2)读到第二个，读入-2,3， 因为-24所以最大差为5， 在 ...
wwwyhx 发表于 2011-2-6 21:09

什么叫读到上升区间为止？
如果是1，-1，3，5，-2，3,0，你这个算法还好使么？应该读完后面的数直到5啊

我的意思是记录波峰波谷，所以记录的数组一定是 a > b, b<c, c>d, d<e 所以如果是数组1，-1，3，5，-2，3,0,-1,-2,7 记录下来就是【 1,-1,5,-2,3,-2，7】不可能出现连续两个递增递减的数，我可能没表达清楚例子也没举好
f(1)考虑1,-1,5, min = -1, maxdist = 6
f(2)考虑-2，3 min = -2, maxdist = (3-(-2)) > maxdist ? maxdist : (3-(-2))
f(3)考虑-2,7   min = -2, .........
一直到f(n)

我的意思是记录波峰波谷，所以记录的数组一定是 a > b, bd, d maxdist ? maxdist : (3-(-2))
f(3)考虑-2,7   min = -2, .........
一直到f(n)
wwwyhx 发表于 2011-2-6 23:48

嗯。我也觉得是你之前没有表述清楚……

我怎么觉得第二题就是遍历的时候维护当前遇到的最小值，然后每次用当前值减当前最小值去更新答案就行了。。。相当于枚举卖出时间。。不过如果题意要求的是实时做出决策，就是在某一点必须做出决定，买进（卖出）或不买进（卖出），那倒一时想不出好的办法，因为缺少点数据分布的信息

赞。。google很喜欢快速排序。。。

greedy algorithm？

为神马跟我当年电面是一摸一样的两道题……后来就悲剧了……后悔没早认识wwwyhx啊!

菜鸟Q1
第1,2个数字，以1/2的概率选中其中一个，记录下来为a
碰到第n个数x_n，以1/N的概率选中x_n，以(1-1/N)的概率选中a，把选中的数记为a
以此类推

证明：如果实际上只有2个数的话，显然.
假设前N-1个数都可以概率1/(N-1)选中的.
如果有N个数的话，第N个数的选中概率为1/N；选中前N-1个数的选中概率为(1-1/N)=(N-1)/N。根据前面的假设，N-1个数都可以按概率1/(N-1)选中，那么现在这些N-1个数的选中概率为1/N。QED。

第一题见过，可以扩展到k个数的情况