airbnb电面

一个数组，选出不相邻子序列，要求子序列和最大，

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

间空间复杂度等。求加分啊～

HouseRobber是假设全部都是正数的，而这个题完全可能有负数。所以状态转移方程要改下。我写了下代码：
int solve(vector<int>& nums) {
  if (nums.empty()) {
    return 0;
  }
  int n = nums.size();
  vector<int> dp(n, 0);
  int res = nums[0];
  dp[0] = nums[0];
  for (int i = 1; i < n; ++i) {
    if (i == 1) {
      dp[i] = max(nums[i], dp[0]);
    }else {
      dp[i] = max(nums[i] + max(dp[i - 2], 0), dp[i - 1]);
    }
    res = max(res, dp[i]);
  }
  return res;
}

storm_hair 发表于 2015-4-5 10:06
这个题我真没看懂是什么意思。。。

如果我没理解错的话，就是要一个隔一个。连续的两个数字是不能加起来的。
所以动态方程应该是
dp[i] = Math.max(dp[i - 1], dp[i - 2] + num[i]);
感觉和leetcode新题house robber是一样的，只不过那个题给你带入了一个具体的情景，让你去盗窃，如果盗窃了相邻的房子就会响警报，所以要一个至少隔着一个偷。

补充内容 (2015-4-5 12:15):
dp[i] = Math.max[dp[i - 1], dp[i - 2] + num[i]);

补充内容 (2015-4-5 12:17):
dp和num后面有个【i】，不知道为什么总是自己消失=-=

A30041839 发表于 2015-11-15 10:08
HouseRobber是假设全部都是正数的，而这个题完全可能有负数。所以状态转移方程要改下。我写了下代码：
int ...

明显不对吧...如果数组全是负数....

lz是网投还是内推还是career fair？

EchoO 发表于 2015-4-5 03:55
lz是网投还是内推还是career fair？

网投。。。。。。。。。。。。。。。

前排支持熟人！
加油加油加油！
这题很像LEETCODE 新题 house robber。

65岁退休 发表于 2015-4-5 06:06
前排支持熟人！
加油加油加油！
这题很像LEETCODE 新题 house robber。

哈哈 你的名字和你一样逗，给加分啊～

mm豆 发表于 2015-4-5 06:19
哈哈 你的名字和你一样逗，给加分啊～

果然是一样的，好久都没看leet了，出了新题也不知道

airbnb 现在待遇怎么样啊？

65岁退休 发表于 2015-4-5 06:06
前排支持熟人！
加油加油加油！
这题很像LEETCODE 新题 house robber。

这个题我真没看懂是什么意思。。。

houqingniao 发表于 2015-4-5 09:26
airbnb 现在待遇怎么样啊？

不清楚                    

能问一下您是最后是怎么得到答复的么？是邮件还是电话？
谢谢了