印度小哥，接到电话直接做题
“玩过打地鼠么”
“一维数组表示一排地洞，1表示有地鼠，0表示没地鼠，有一个锤子宽度是N, 最多能打几个地鼠。”
-算法+时间复杂度+能优化么
“现在有2个锤子，能打几个地鼠”
-算法+时间复杂度+写代码+跑一个用例
“good luck”
真是 来也匆匆去也匆匆恨不能相逢，爱也匆匆恨也匆匆一切都随风
两个锤子可以做到O(N)，用一维memoization，左往右扫一遍记下所有 0~i 范围能打的最多地鼠，右往左扫一遍记下所有 i~n范围能打的最多地鼠，在扫一遍求max，max = max(currentMax, 这个锤子+左锤子， 这个锤子+右锤子)，把“这个锤子”在数组里扫一遍就可以
补充内容 (2018-10-30 21:53):
我的做法还是偏复杂了，其实这题的主要思路就是Buy and Sell Stock Twice
这解法感觉不对。比如假设地鼠分布为0100110110010，锤子宽度为5，两个锤子分别在10011 和11001上时达到最大值，但此时两个锤子位置相距1个位置。似乎，、需要针对两个锤子相距位置从0到N-1的N种情况各自再扫描一遍才能确定最后的最大值。
follow up 3 steps: O(1) space, O(n) time
- travel one time to find max with position (any is ok): a
- travel another time to find max that not overlap the position in 1: b
- travel another time to find max with width 2N: c
the answer would be max(a+b, c)
请问楼主，这样的想法不知道对不对。
两个锤子一起用，有可能是挨在一起，有可能是分开用，求两种情况的最大值即可。
第一种情况：用一个2*width的window求能打到地鼠的最大值。
第二种情况：运行两遍一个锤子的打地鼠，只是第一遍打了的地鼠归零，求出两遍的最大和。
求问 Followup怎么解？
window一遍扫过去？
线性时间？
我是不是想简单了。。
同问followup怎么解？
sliding window问题？优化难道用segment tree?
同问follow up
SEE YA GOGO
类似于dp zszszszs