一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 1294|回复: 14
收起左侧

SnapChat电面

[复制链接] |试试Instant~ |关注本帖
mm豆 发表于 2015-2-4 05:21:41 | 显示全部楼层 |阅读模式

2015(1-3月) 码农类 硕士 全职@snapchat - 网上海投 - 技术电面 |Fail

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
给定数组,只有正数,使用+和*和()。求最大值。
使用DP解决。dp[j] = max(dp[m - 1] + dp[m][j], dp[m - 1] * dp[m][j]);
. 鍥磋鎴戜滑@1point 3 acres


补充内容 (2015-2-8 08:09):
dp[0][len] = max(dp[0][m] + dp[m][len], dp[0][m] + dp[m][len]), m = 0...len.

评分

2

查看全部评分

wangxinlei 发表于 2015-4-21 07:51:14 | 显示全部楼层
hno3 发表于 2015-3-12 13:24
谢谢回复,感觉清楚多了

补充内容 (2015-3-12 13:28):

当i大于等于4时候,一定可以将这些数分为两个集合,每个集合有多于等于2个数,也就保证每个集合最大值肯定大于1。而如果两个大于1的集合,一定是乘才会得到最大值。
回复 支持 2 反对 0

使用道具 举报

tangtianlei 发表于 2015-2-4 06:40:36 | 显示全部楼层
楼主这里dp[m][j]是什么东西啊 没看明白,能解释下么
回复 支持 反对

使用道具 举报

qjx026 发表于 2015-2-4 08:31:07 | 显示全部楼层
请问 dp 是一维数组么?  dp[m][j] 是什么?
max() 是调用的递归函数么? -google 1point3acres
不明觉厉
回复 支持 反对

使用道具 举报

头像被屏蔽
whuwangyi 发表于 2015-2-4 15:26:49 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复 支持 反对

使用道具 举报

 楼主| mm豆 发表于 2015-2-8 08:03:26 | 显示全部楼层
whuwangyi 发表于 2015-2-4 15:26
我电面也是这一道题目,是一个ABC出的么?.鐣欏璁哄潧-涓浜-涓夊垎鍦
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
LZ的DP看得不太明白,我的做法是O(N^3)复杂度,很好奇O(N^2) ...

你过了么?
回复 支持 反对

使用道具 举报

 楼主| mm豆 发表于 2015-2-8 08:48:22 | 显示全部楼层
tangtianlei 发表于 2015-2-4 06:40
楼主这里dp[m][j]是什么东西啊 没看明白,能解释下么

抱歉,写错了     
回复 支持 反对

使用道具 举报

 楼主| mm豆 发表于 2015-2-8 08:48:44 | 显示全部楼层
qjx026 发表于 2015-2-4 08:31
请问 dp 是一维数组么?  dp[m][j] 是什么?
max() 是调用的递归函数么?
不明觉厉

不是递归,使用dp循环
回复 支持 反对

使用道具 举报

wgtmac 发表于 2015-2-8 10:27:02 | 显示全部楼层
一维DP就够了吧
  1.       
  2.         int[] k = new int[A.length];
  3.         k[0] = A[0];
  4.         
  5.         for (int i = 1; i < A.length; i++) {
  6.             k[i] = Math.max(k[i - 1] * A[i], (i >= 2 ? k[i - 2] : 1) * (A[i - 1] + A[i]));

  7.             if (i - 2 >= 0) {
  8.                 k[i] = Math.max(k[i], (i >= 3 ? k[i - 3] : 1) * (A[i - 2] + A[i - 1] + A[i]));
  9.             }. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  10.         }
复制代码
回复 支持 反对

使用道具 举报

头像被屏蔽
whuwangyi 发表于 2015-2-8 10:28:28 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复 支持 反对

使用道具 举报

traceroute_su 发表于 2015-3-9 09:31:24 | 显示全部楼层
若二维数组 肯定要N^3吧 大赞8楼代码 省去很多无用功  . 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
2D dp
State: dp[i,j] 从i到j 最大的表达式和
Transition equation: dp(i,j) = Max{dp[i,m]*dp[m+1,j]}, m = i..j.
结果在dp[0,n];

1D dp:
State: dp[i] 到i的最大表达式和. 1point 3acres 璁哄潧
Transition equation: dp[i] = Max{dp(j)*sum(a[k])}, j = i-3 ... i-1, k = j+1,i
.鐣欏璁哄潧-涓浜-涓夊垎鍦
回复 支持 反对

使用道具 举报

hno3 发表于 2015-3-12 13:24:43 | 显示全部楼层
traceroute_su 发表于 2015-3-9 09:31
若二维数组 肯定要N^3吧 大赞8楼代码 省去很多无用功  
2D dp-google 1point3acres
State: dp 从i到j 最大的表达式和

谢谢回复,感觉清楚多了 鏉ユ簮涓浜.涓夊垎鍦拌鍧.

补充内容 (2015-3-12 13:28):
弱弱的问问,怎么证明一维只需要比较后三个的值。。。
回复 支持 反对

使用道具 举报

traceroute_su 发表于 2015-3-13 02:21:06 | 显示全部楼层
hno3 发表于 2015-3-12 13:24
谢谢回复,感觉清楚多了

补充内容 (2015-3-12 13:28):

其实证明很简单,列出组合,删除掉小值,剩下的肯定是大值,因为所有值都是>=1的
回复 支持 反对

使用道具 举报

EchoO 发表于 2015-3-14 03:01:12 | 显示全部楼层
lz是网申,refer还是career fair?
回复 支持 反对

使用道具 举报

magicalcan 发表于 2015-4-29 14:23:15 | 显示全部楼层
wangxinlei 发表于 2015-4-21 07:51
当i大于等于4时候,一定可以将这些数分为两个集合,每个集合有多于等于2个数,也就保证每个集合最大值肯 ...
.1point3acres缃
嗯,这个解释的清晰
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-10 07:43

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表