Page 37
“前后两个子序列的总和最大区间中间有间隔,我们假定这两个子序列的总和最大区间分别是[p1,q1]和[p2,q2]。这时,整个序列的总和最大区间是下面三者中的最大的那一个:
(1)[p1,q1]
(2)[p2,q2]
(3)[p1,q2]”
但是,这个可以提出一个反例
序列:
[1,4,-10,4,-1,-2,3,4]
子序列为[1,4,-10,4]和[-1,-2,3,4]
则[p1,q1]对应的子序列为[1,4]
[p2,q2]对应的子序列为[3,4]
[p1,q2]对应的子序列为[1,4,-10,6,-1,-2,3,4]
然后存在总和更大的区间[6,-1,-2,3,4]
事实上,这种反例很容易找出来。最简单的就是[K,q2] > [p2,q2],但[p1,K]<[p1,q1]。
感觉分治法并不适合"区间问题",更适合单点问题,除非可以找到解决合并后gap的处理方法。
不知道是不是我理解有错误,欢迎指正。
网友评论