Google面试跪经

mingzhou1987 发表于 2016-3-4 16:01
有负数是不是，迭代方程式变成dp = max(dp, dp, dp + nums)?

我觉得是的，我就是
if dp[i-2] < 0 dp[i] = max(nums[i], dp[i-1])
else dp[i] = max(nums[i]+dp[i－2], dp[i-1])
和你说的一样

补充内容 (2016-3-5 01:38):
哦不对，貌似下面这个例子你的迭代方程式算出来的不对
－2， 3， 4，－9，－1，10
按照你的算法，结果是13 而不是14

youdidut 发表于 2016-3-4 10:02
社交网络推荐好友是什么题啊？能详细讲一下题和解题思路吗？

题目参见10楼，我不会做，最后用的是暴力解法。
比如a-b, a-c, b-d, b-e, c-d这种，就先直接找出a的好友，在找出a好友的好友，看谁出现的次数最多，感觉挺笨的

递推方程应该是这样吧:

if(A[n]>0)  dp[n] = max(dp[n-1], dp[n-2] + A[n])
if(A[n]<=0) dp[n] = dp[n-1]

解释为，如果当前值大于0,那么可以取，也可以不取，正常情况，如果小于0, 那么一定不取。