Facebook面经题讨论

Job Hunting Interview
,
1

看到一个面经题，是maximum sum of non-overlapping subarray 的改版。

一个数组[1,5,2,-2,3,4], k = 3 它让求两个interval的和的最大值，问题是，不是这两个interval分别长k，而是加起来为k……比如k=3就是分成（1，2）长度的interval（0，3这种不算）也就是说这道题答案是（5）+（3+4）= 12.

我只能想到n*k的做法，就是从头扫，找到0-i之间长度为L的最大subarray sum；然后再从尾扫，找到n-1 - j的长度为L的最大subarray sum；然后再扫一遍 每次找MAX(array1[i][m] + array2[i+1][k-m]))。 大家对这题有什么好的解法吗?

2

可以这样试试：
找出从左到某个index为止的长为 m 的interval的最大值，记为 left[index][m]
找出从右到某个index为止的长为 m 的interval的最大值，记为 right[index][m]

m的大小是1,2,3, …, k - 1。
当选定某个index，找 max(left[index][m] + right[index][k - m])

3

多谢x老师。我现在想到的方法也只有这个，时间复杂度就是3KN

4

哦，是同一种解法。这个解法不够好吗？

5

感觉有点麻烦，毕竟要扫三遍，不知道有没有什么更好的办法。

6

你把第二遍和第三遍合并，稍微优化一点

7

哦哦，哦哦，有道理。那看来整体思路应该就是这样了。