C最大子数组
作者:weinee / 发布于2015/4/8/ 600

使用分治算法解决最大子数组和问题,问题描述如下:
给定一个整数序列 S,找出 S 中的连续子序列,使得该子序列和最大,要
求算法时间复杂性为 Θ(nlogn)。例如:-2, 11, -4, 13, -5, -2; 结果为 20: (11,
-4, 13)。
提示:
假定要寻找子数组 S[low…high]的最大子数组,使用分治法将数组分解成
两个尽可能想相等的子数组,找到子数组中点 mid,则 S[low…high]中任何连
续数组 S[i…j]必然是一下三种情况之一:
? 完全位于 S[low…mid]中, low≤i≤j≤mid
? 完全位于 S[mid+1…high]中, mid<i≤j≤high
? 跨越中点 mid, low≤i≤mid<j≤high
因此, S[low…high]的一个最大子数组所处的位置必然是三种情况之一。
可以通过递归方法求解 A[low…mid]和 A[mid+1…high]的最大子数组,则剩
下的问题就是求解跨越中点的最大子数组,然后在三种情况下选择最大者。

评论列表