首页 > 代码库 > 使用分治算法求解最大子数组问题
使用分治算法求解最大子数组问题
def MaxCrossSubarray(num,mid,low,high): leftsum=0 leftmax=-1000000 rightsum=0 rightmax=-1000000 for i in range(mid,low-1,-1): leftsum=leftsum+num[i] if leftsum>leftmax: leftmax=leftsum leftlow=i for j in range(mid+1,high+1): rightsum=rightsum+num[j] if rightsum>rightmax: rightmax=rightsum righthigh=j sum=leftmax+rightmax return (leftlow,righthigh,sum) def MaxSubarray(num,low,high): if low==high: return (low,high,num[low]) else: mid=(low+high)//2 (left_low,left_high,left_sum)=MaxSubarray(num,low,mid) (right_low,right_high,right_sum)=MaxSubarray(num,mid+1,high) (cross_low,cross_high,cross_sum)=MaxCrossSubarray(num,mid,low,high) if(left_sum>right_sum and left_sum>cross_sum): return (left_low,left_high,left_sum) elif(right_sum>left_sum and right_sum>cross_sum): return (right_low,right_high,right_sum) elif(cross_sum>left_sum and cross_sum>right_sum): return (cross_low,cross_high,cross_sum) a=[13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7] max = MaxSubarray(a, 0, len(a)-1) print max
使用分治算法求解最大子数组问题
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。