美文网首页
计算之魂 1.3节分治法中的错误?

计算之魂 1.3节分治法中的错误?

作者: 景天儿 | 来源:发表于2022-09-13 22:50 被阅读0次

    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的处理方法。

    不知道是不是我理解有错误,欢迎指正。

    相关文章

      网友评论

          本文标题:计算之魂 1.3节分治法中的错误?

          本文链接:https://www.haomeiwen.com/subject/hmxkortx.html