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的处理方法。
不知道是不是我理解有错误，欢迎指正。
Page 37“前后两个子序列的总和最大区间中间有间隔，我们假定这两个子序列的总和最大区间分别是[p1,q1]和[...
分治和回溯本质上都是递归。 分治 Divide & Conquer 在计算机科学中，分治法是建基于多项分支递归的一...
算法之 分治法 Divide and Conquer 分治法： 分治法的设计思想是：将一个难以直接解决的大问题，分...
分治法 定义 在计算机科学中，分治法是建基于多项分支递归的一种很重要的算法范式。字面上的解释是“分而治之”，就是把...
分布式计算模式：MapReduce 什么是分治法？ 分治法是将一个复杂、难以直接解决的大问题，分割成一些规模小、可...
分治法是一种非常通用的算法设计技巧. 在很多实际问题中, 相比直接求解, 分治法往往能显著降低算法的计算复杂度. ...
分治算法 一、基本概念 在计算机科学中，分治法是一种很重要的算法。字面上的解释是“分而治之”，就是把一个复杂的问题...
分治算法 一、基本概念 在计算机科学中，分治法是一种很重要的算法。字面上的解释是“分而治之”，就是把一个复杂的问题...
五大常用算法之一：分治算法 一、基本概念 在计算机科学中，分治法是一种很重要的算法。字面上的解释是“分而治之”，就...
分治算法简介 在计算机科学中，分治法是一种很重要的算法。字面上的解释是“分而治之”，简单来说就是把一个问题分解为很...
本文标题：计算之魂 1.3节分治法中的错误？
本文链接：https://www.haomeiwen.com/subject/hmxkortx.html
网友评论