FB Onsite

surdcn 发表于 2017-3-10 23:01
切分成三段，记忆最右边窗口，左边两个移动的时候每次比较新的可能的窗口，更新现在最大的窗口

请忽略看下面的O(n) dp

abrahamf 发表于 2017-3-11 01:41
这个其实可以优化到O(n)时间。
建从左端到每个下标的最大window数组，再建从右端到每个下标的最大window ...

能解释一下吗？

RedDevils 发表于 2017-3-11 02:12
能解释一下吗？

贴个我自己的解，供批判。。。。

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

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

abrahamf 发表于 2017-3-11 12:18
贴个我自己的解，供批判。。。。

我觉得思路是对的, 但是代码是不是有bug啊? 像sums = s这种语句, 怎么直接把一个整数赋给一个vector了...

abrahamf 发表于 2017-3-11 12:18
贴个我自己的解，供批判。。。。

ans 应该是这样的吧

1. ans = Math.max(ans, left[i - k] + (sums[i] - sums[i - k]) + right[i + 1]);

复制代码

补充内容 (2017-4-24 14:08):
我说错了，楼主是对的

lhh_NJU 发表于 2017-3-13 14:32
我觉得思路是对的, 但是代码是不是有bug啊? 像sums = s这种语句, 怎么直接把一个整数赋给一个vector了.. ...

是网站的原因，[ i ] 会变成斜的

1. sums[i] = s
   

复制代码

abrahamf 发表于 2017-3-11 01:41
这个其实可以优化到O(n)时间。
建从左端到每个下标的最大window数组，再建从右端到每个下标的最大window ...

木有理解。。。请问能给点代码么。。。谢了。