问一个脸熟电面题

给一个数组, 和一个size
一问, 求给定size Sum最大的subarray(连续)
二问, 如果求三个 给定size

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

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

017-9-21 10:47):
请忽略例子的第一个数组

ws775901 发表于 2017-9-21 14:29
可以具体说一下dp怎么做的吗？这两个dp数组是代表什么意思，traverse中间又是什么意思。还有个问题，比如 ...

不能重复
先从左到右做个dp存以这个idx为最后的max sliding window值
举个例子[2,3,2,2,6,1,6], size = 2
存法是[x,5,5,5,8,8,8], x代表那个数不管，不在sliding window内
以此类推从右往左就变成[8,8,8,8,7,7,x]
最后从中间重新sliding window traverse 配合那两个dp array取max sum就好
这个例子的话就是5 + 8 + 7 = 20

大致上是这样吧

leetcode已经有这道新题了

GardenAAA 发表于 2017-9-26 03:05
能解释一下这一步吗，最后从中间重新sliding window traverse 配合那两个dp array取max sum就好，谢谢大 ...

这个意思是指，
1. 一开始你有一个从左边扫好的left_dp array，这个array再每一个的节点的意思是说，在这个节点以左的最大sliding window值，
2. 同样做法做一次从右边扫right_dp，意思一样是在这个节点以右的最大sliding window max值
3. 最后你只要从offset k ~ len - k - 1去找所有valid 的middle part sliding window，每找到一个sliding window，left_dp[cur-k] + cur_val + right_dp[cur+1] 就是你这个sliding window所能组成的最大3 sliding window max值，按照这个思路做下去就好了

我朋友onsite遇到这道题了没做好，O(n^2)的挺好写的，面试官好像说最优是O(n)

上帝是童话 发表于 2017-9-21 12:10
我朋友onsite遇到这道题了没做好，O(n^2)的挺好写的，面试官好像说最优是O(n)

O(n)是指找三个吗 ? 因为那样的话可以O(3n)做出来, 还是不论找多少个都可以做到 O(n)?

给定了size，就用这个size的window在array上sliding可以做吗？还是我理解错了？

ojjccc 发表于 2017-9-21 12:23
给定了size，就用这个size的window在array上sliding可以做吗？还是我理解错了？

可以的, 第一问比较简单, 第二问比较麻烦, 就算是Sliding window的话

这个是用dp做的，
从左到右做一个left dp array，
从右到左在做一个right dp array，
最后traverse中间的部分找最大值就好

总共三次for的sliding window循环，所以是O(3n) 最后可以说成是O(n)

我ONSITE碰到，第二问我用了DP，时间复杂度是O（N），就是因为是新题，不知道我写对了没有。最后feedback说有一轮coding是中等所以没有发OFFER，也不知道是不是这一轮。

chris612ku 发表于 2017-9-21 13:08
这个是用dp做的，
从左到右做一个left dp array，
从右到左在做一个right dp array，

可以具体说一下dp怎么做的吗？这两个dp数组是代表什么意思，traverse中间又是什么意思。还有个问题，比如1,2,3,4,5,6,7,8,9size=3,三个最大的subarray是不是7,8,9;6,7,8;5,6,7?

chris612ku 发表于 2017-9-21 14:54
不能重复
先从左到右做个dp存以这个idx为最后的max sliding window值
举个例子[2,3,2,2,6,1,6], size = ...

多谢回复，有一个例子我不确定是哪一个答案对：
[1, 2, 6, 2, 5, 1, 1]. Size=2 一种解是8，7，2；另一种解是3，8，6。