问一个脸熟电面题

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

腻害 !感觉很巧妙, 但是不用Dp的话, 感觉也可以做到O(n), 直接三次遍历, 每一次用过Index都放在一个Hashset, 下次遍历的时候维护一个start Index和end Index, 一开始把start Index和end Index定位到第一个没用的index, 然后end index向后扫, 一遇到用过的index, start index和end index一起重新定位到下个可用的Index, 这也可以扩展不止求三个, 感觉可行 ?

strisunshine 发表于 2017-9-21 20:24
腻害 !感觉很巧妙, 但是不用Dp的话, 感觉也可以做到O(n), 直接三次遍历, 每一次用过Index都放在一个Hashs ...

有一个问题，如果直接用index扫的话，是有可能得不到最优解的。比如[1, 2, 6, 2, 5, 1, 2]. size = 2这个例子里有两种解法 一种是(2, 6), (2, 5), (1, 2). 另一种是(6, 2), (5, 1), (1, 2)。所以当遇到2个最大值后，不能确定选哪个可以使得第二个解最大。

ws775901 发表于 2017-9-22 02:25
有一个问题，如果直接用index扫的话，是有可能得不到最优解的。比如[1, 2, 6, 2, 5, 1, 2]. size = 2这个 ...

恩, 你说的对哎

ws775901 发表于 2017-9-21 16:46
多谢回复，有一个例子我不确定是哪一个答案对：
[1, 2, 6, 2, 5, 1, 1]. Size=2 一种解是8，7，2；另一种 ...

根据面经来看的话没所谓的，面试官只要求返回最大值，不要求组合
以防万一的话，面试的时候问一下面试官交流交流，顺便在沟通分数上面加分也是挺好的

strisunshine 发表于 2017-9-21 20:24
腻害 !感觉很巧妙, 但是不用Dp的话, 感觉也可以做到O(n), 直接三次遍历, 每一次用过Index都放在一个Hashs ...

看起来好像没有到很可行。。。但我也只是凭空想象，并没有实际implement过
如果看到代码的话应该更容易看work不work？

strisunshine 发表于 2017-9-21 12:15
O(n)是指找三个吗 ? 因为那样的话可以O(3n)做出来, 还是不论找多少个都可以做到 O(n)?

感觉只有三个才能做到O(n)，如果更多的话，要O(n^2) DP了吧

ws775901 发表于 2017-9-22 02:25
有一个问题，如果直接用index扫的话，是有可能得不到最优解的。比如[1, 2, 6, 2, 5, 1, 2]. size = 2这个 ...

又想起了这道题, 假如以下这种情况:
7 8 8 6 6 3 2, size 2
这里要看这道题怎么定义这个3 Max sum, 如果是只要找全局 (3个Sum之和) 最优, DP的解法找到的就是对的:
(7, 8), (8, 6), (3, 2)
但我当时通过面试官的说法理解到的是每找一个Max sum应该是当前最优 (当时在面试时试图跟面试官讨论这个, 但是当时只有模糊概念, 没有清楚地表述, 而面试官好像也没有觉得有Clarify的必要), 如果每找一个Max sum都得是当前最优的话, 答案应该是
(8, 8), (6, 6), (3,2)
所以这道题搞不清楚定义还是有点蒙

补充内容 (2017-9-25 13:17):
以上例子错, 换成这个:
7 8 8 6 6 5 5  size 2
DP解法会找到：
（7 8） （8 6） （6 5） 5
以另一种理解会找到:
7 （8 8） （6 6） （5 5）  
还看怎么定义

strisunshine 发表于 2017-9-25 13:10
又想起了这道题, 假如以下这种情况:
7 8 8 6 6 3 2, size 2
这里要看这道题怎么定义这个3 Max sum, 如 ...

呃 举的例子错了, 我再想想

第一问很简单，用window遍历一遍就行；
第二问遍历三遍，只不过遇到以前的index时跳过去就好。
不知道我有没有理解错？