本文共 3287 字，大约阅读时间需要 10 分钟。
简单的分治策略
分治，是编程中常用的一种策略，例如在归并排序中就有使用。分治策略是一种递归求解问题的方法，在每层的递归中可分为三个步骤：分解（divide）、解决（conquer）、合并（combine）。分解（divide）指的是将问题划分为一些子问题，子问题与原问题具有相同的形式，但规模较之更小。解决（conquer）指的是递归的求解子问题，当问题规模足够小时，直接求解并开始回溯。合并（combine）指的是将子问题得到的解进行合并。在问题规模较大，需要递归求解的时候称之为递归情况（recursive case），子问题规模足够小时，出现“触底”时，就进入了可直接解决的基本情况（base case）。
下面分析利用分治策略处理区域内峰值问题的简单例子：求数组的最大子数组之和。
假定有一个整型数组Arr[low~high]（为了简化过程，使用简单数据类型加以介绍，并且规定该数组中元素数量不低于1个，不大于1000个），现需求出该数组中的一个和最大的子数组以及它的和值。现在我们进行简单分析，要得到该子数组，我们需要知道它在原数组中的边界。原数组可能可以划分出一个或一个以上的子数组，而和最大便成了我们找寻的依据。
对问题进行分解，假定Arr[i~j]是我们要求的数组，那么原问题可以分成规模更小的问题，完全位于子数组Arr[low~mid]，完全位于子数组Arr[mid+1~high] ,跨越中点mid(mid的值为(low+high)/2)。得到了规模更小的问题后，我们就可以对完全位于子数组Arr[low~mid]和完全位于子数组Arr[mid+1~high]这两个规模更小的问题进行递归求解了。然后我们只需要对跨越中点mid这种情况在单独处理下，我们就能够得到每层递归中的子问题的解了，然后再对子问题的解合并，当然这里并不是意味着相加，而是依据我们的条件选择和处理。
现在对子问题进行处理流程分析。先从特殊的情况开始：
1、计算low到mid范围内的和值，记为左最大和值。
2、计算mid+1到high范围内的和值，记为右最大和值。
3、计算左最大和右最大的和，记为跨越中点最大和值。
然后是完全位于子数组Arr[low~mid]，完全位于子数组Arr[mid+1~high]这两种情况，实际上这是处理上等同的情况，因为我们只需要同原问题一样分解处理直到触底发生。所以我们需要：
1、 先判断触底是否发生，触底情况为low和high相等，此时只有一个元素，和值就为该元素本身。
2、 获取左最大
3、 获取右最大
4、 获取跨越中点最大
5、 合并处理三个最大，得到符合条件的子数组和它的和值。
下面给出该问题的C语言主要源码：
#include#include typedefstruct data{ int left; int right; long long int sum;}Data; voidfindCrossSubArr(long int *arr,int low,int mid,int high,Data *crossResult){ long long int left_sum=INT_MIN; // INT_MIN, C标准中定义的最小数 long long int right_sum=INT_MIN; long long int sum=0; int I, j; //左 for(i=mid;i>=low;i--) { sum=sum+arr[i]; if(sum>left_sum) { left_sum=sum; crossResult->left=i; } } //右 sum=0; for(j=mid+1;j<=high;j++) { sum=sum+arr[j]; if(sum>right_sum) { right_sum=sum; crossResult->right=j; } } crossResult->sum=left_sum+right_sum; retutn ;} voidfindMaxSubArr(long int *arr,int low,int high,Data *result){ Data leftResult,rightResult,crossResult; int mid=(low+high)/2; //除以2 // 触底情况处理 if(low==high) //只有一个元素 { result->left=low; result->right=low; result->sum=arr[low]; return; } //分解、解决部分 findMaxSubArr(arr,low,mid,&leftResult); // 左 findMaxSubArr(arr,mid+1,high,&rightResult); // 右 findCrossSubArr(arr,low,mid,high,&crossResult); // 跨越中点 // 合并处理部分 // 左 if((leftResult.sum)>=(rightResult.sum)&&(leftResult.sum)>=(crossResult.sum)) { result->left=leftResult.left; result->right=leftResult.right; result->sum=leftResult.sum; return ; } // 右 elseif((rightResult.sum)>=(leftResult.sum)&&(rightResult.sum)>=(crossResult.sum)) { result->left=rightResult.left; result->right=rightResult.right; result->sum=rightResult.sum; return ; } // 跨越中点 else { result->left=crossResult.left; result->right=crossResult.right; result->sum=crossResult.sum; return ; } } intmain(void){ Data result; long int arr[]; // 此处添加输入数据代码》》》》 findMaxSubArr(arr,low,high,&result); // 此处添加结果输出代码》》》》 return 0;}
转载地址：http://tmmsi.baihongyu.com/