问一个脸熟电面题

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

能解释一下这一步吗，最后从中间重新sliding window traverse 配合那两个dp array取max sum就好，谢谢大神

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值，按照这个思路做下去就好了

tekkaman 发表于 2017-9-26 02:26
一直听说fb有这道题，但是不知道具体要求是什么。我说一个刚刚想出的思路（按照lz的题目要求）：选最大的连 ...

我也用的同样的想法, 然后觉得移除简单点, 结果发现不行, 移除的话会把原来不相连的连一起, 标记应该是可以的, 看题目要求

chris612ku 发表于 2017-9-26 06:05
这个意思是指，
1. 一开始你有一个从左边扫好的left_dp array，这个array再每一个的节点的意思是说，在 ...

还是有个疑问想请教一下
以下这个例子应该返回什么呢？
7 8 8 6 6 5 5  size 2

面试中我也是没有搞清楚这一点, 是应该只考虑全局最优吗, 就是个3个Sum之和最大最行, 不管单独的, 像以下:
（7 8） （8 6） （6 5） 5

还是每找一个Sum 都应该是当前最优的, 像以下:
7 （8 8） （6 6） （5 5）  

我一开始理解的是后一种, 感觉按DP返回的是前一种

strisunshine 发表于 2017-9-27 07:25
还是有个疑问想请教一下
以下这个例子应该返回什么呢？
7 8 8 6 6 5 5  size 2

个人觉得是整体的最大，应该不需要去考虑单独的问题，
这样才比较像个面试题。。。
感觉如果还要管单独的。。。这不是到太好写。。。

但这纯属个人意见啦。。。不代表真的，自己没碰过这道题

tekkaman 发表于 2017-9-27 09:37
连在一起也没有关系啊，比如第一次选出的index是2，3，4，而第二次是1，5，6，那么其实这两个窗口就是1， ...

请见楼上的讨论, 这个是基于哪种要求的呀, 是全局最优就可以了, 还是每次都要局部最优呢 ?

chris612ku 发表于 2017-9-26 06:05
这个意思是指，
1. 一开始你有一个从左边扫好的left_dp array，这个array再每一个的节点的意思是说，在 ...

没怎么看懂，能具体举例子说明一下吗？

onein 发表于 2017-9-28 09:57
没怎么看懂，能具体举例子说明一下吗？

先从左到右做个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