Page 37
“前后兩個(gè)子序列的總和最大區(qū)間中間有間隔逻杖，我們假定這兩個(gè)子序列的總和最大區(qū)間分別是[p1,q1]和[p2,q2]。這時(shí)澳厢，整個(gè)序列的總和最大區(qū)間是下面三者中的最大的那一個(gè)：
(1)[p1,q1]
(2)[p2,q2]
(3)[p1,q2]”
但是环础，這個(gè)可以提出一個(gè)反例
序列：
[1,4,-10,4,-1,-2,3,4]
子序列為[1,4,-10,4]和[-1,-2,3,4]
則[p1,q1]對(duì)應(yīng)的子序列為[1,4]
[p2,q2]對(duì)應(yīng)的子序列為[3,4]
[p1,q2]對(duì)應(yīng)的子序列為[1,4,-10,6,-1,-2,3,4]
然后存在總和更大的區(qū)間[6,-1,-2,3,4]
事實(shí)上，這種反例很容易找出來(lái)剩拢。最簡(jiǎn)單的就是[K,q2] > [p2,q2]线得，但[p1,K]<[p1,q1]。
感覺分治法并不適合"區(qū)間問題"徐伐，更適合單點(diǎn)問題贯钩，除非可以找到解決合并后gap的處理方法。
不知道是不是我理解有錯(cuò)誤，歡迎指正角雷。
