首页 > 代码库 > 分治算法——最大子数组
分治算法——最大子数组
表示很久没有接触算法了，好多东西真心要一点点拾掇起来，为了找份好工作，我也是蛮拼的了。
好吧，下来说说分治算法，因为在leetcode上刚好碰到这么个问题，想到要用分治做，但是一时又不清楚具体步骤。于是抱起《算法导论》啃起来。刚好上面的例子也是这个算法，就研读了一下。
假定，我们要寻找子数组A[low...high]的最大字数组，使用分治算法，其结果必定是以下三种情况中的一个：
1.完全位于子数组A[low...mid]中，因此low <= i <= j <= mid
2.完全位于子数组A[mid+1...high]中，因此mid < i <= j <= high
3.在mid位置的两边，包含mid位置。因此low <= i <= mid < j <= high
对于1和2，我们可以递归地求解，将他们子问题的结果逐层往上返回，就获得mid左右两边的最大字数组（但不包括情况3）。现在我们要做的，就是针对情况3，进行处理。
函数代码如下：
def cross_mid_maxsub(self,A,low,mid,high): left_s = float(‘-inf‘) #当前最大值，默认负无穷 sum = 0 #我们得到的子串的和 for i in range(mid,low-1,-1): #因为一定要有mid，故从mid开始 sum += A[i] if sum > left_s: left_s = sum max_left = i #记录最大子串左侧起始位置 right_s = float(‘-inf‘) sum = 0 for i in range(mid+1,high+1): sum += A[i] if sum > right_s : right_s = sum max_right = i #记录最大子串左侧起始位置 return （max_left , max_right , left_s + right_s）
好了，现在3种情况都已经搞定了。下面就可以直接递归求解了。
def max_sub(self,A, low, high): if high == low: #防止只有1个元素的情况 return (low, high, A[low]) else: mid = (low+high)/2 left_low, left_high, left_s = max_sub(self, A, low, mid) #递归求情况1 right_low, right_high, right_s = max_sub(self, A, mid+1, high) #递归求情况2 cross_low, cross_high, cross_sum = cross_mid_maxsub(self, A, low, mid, high) #递归求情况3 if left_s >= right_s and left_s >= cross_sum: return left_low, left_high, left_s elif right_s >= left_s and right_s >= cross_sum: return right_low, right_high, right_s else: return cross_low, cross_high, cross_sum
上面的步骤是，先递归地找出情况1的最大值，然后找出情况2的最大值，然后找出包含mid的，也就是情况3的最大值。然后比较一下，返回其中的最大值，再回溯到上一层继续求。基本的思路是这样的了。其实这还是个比较简单的算法嘛~
分治算法——最大子数组
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。