简单分治
在之前的排序算法中，我们提到了一种叫归并排序的算法，就是通过把待排序的数列分成一个个小的数列并排序成有序表，再将这些小的有序表组合成一个新的有序表来完成排序，所以归并排序算法就是利用分治策略的一个很好的典型。
概念阐述
在分治策略中我们用递归的方法来求解一个问题，在每一层的递归中应用如下的三个步骤：
- 分解(Dived)步骤将问题划分为一些子问题，子问题的形式与原问题一样，只是规模更小。
- 解决(Conquer)步骤递归地求解出子问题。如果子问题的规模足够小，则停止递归，直接求解。
- 合并(Combine)步骤将子问题的解组合成原问题的解。
简单通俗地来说，所谓的分治策略就是把很复杂的问题用递归的方式细化成一个个小的，能够解决子问题，再把所有子问题的解合并起来，就得到原问题的解。
下面就通过一个例子来简单介绍分治策略。
实例问题
这里有一个数组A：
[13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7]
现在要求寻找数组A中和最大的非空连续子数组（我们称这样的连续子数组为最大子数组）。
暴力求解法
乍一看到这个问题，首先想到的当然就是简单粗暴地套上双重循环，尝试每对可能的组合，再进行比较，得出最终结果，这就是我们常说的暴力求解法，算法实现如下：
1 | //最大子数组问题：暴力求解法 |
FIND-MAX-CROSSING-SUBARRRY( A, low, mid, high )
left-sum = -100000
sum = 0
for i = mid downto low
sum = sum + A[i]
if sum > left-sum
left-sum = sum
max-left = i
right-sum = -100000
sum = 0
for j = mid + 1 to high
sum = sum + A[i]
if sum > right-sum
right-sum = sum
max-right = j
return (max-left, max-right, left-sum + right-sum)
1 |
|
FIND-MAXIMUM-SUBARRAY(A, low, high)
if high == low
return ( low, high, A[low] );
else
mid = ( low + high ) / 2
( left-low, left-high, left-sum ) =
FIND-MAXIMUM-SUBARRAY( A, low, mid )
( right-low, right-high, right-sum ) =
FIND-MAXIMUM-SUBARRAY( A, mid + 1, high )
( cross-low, cross-high, cross-sum ) =
FIND-MAX-CROSSING-SUBARRRY( A, low, mid, high )
if left-sum >= right-sum and left-sum >= cross-sum
return ( left-low, left-high, left-sum )
elseif right-sum >= left-sum and right-sum >= cross-sum
return ( right-low, right-high, right-sum )
else
return ( cross-low, cross-high, cross-sum )1
2
3
4
5
6
具体实现代码如下：
//最大子数组问题：分治策略法
#include <stdio.h>
int last_low, last_high;
int
find_max_cro_arr( int A[], int low, int mid, int high )
{
int i, j;
int left_sum = -100000;
int sum = 0;
for( i = mid; i >= low; i– ){
sum += A[ i ];
if( sum > left_sum )
{
left_sum = sum;
last_low = i;
}
}
int right_sum = -100000;
sum = 0;
for( j = mid + 1; j <= high; j++ ){
sum = sum + A[ j ];
if( sum > right_sum )
{
right_sum = sum;
last_high = j;
}
}
return left_sum + right_sum;
}
int
find_max_arr( int A[], int low, int high )
{
int left_sum, right_sum, cross_sum;
if( high == low )
return A[ low ];
else
{
int mid = ( low + high ) / 2;
left_sum = find_max_arr( A, low, mid );
right_sum = find_max_arr( A, mid + 1, high );
cross_sum = find_max_cro_arr( A, low, mid, high );
if ( left_sum >= right_sum && left_sum >= cross_sum )
return left_sum;
else if ( right_sum >= left_sum && right_sum >= cross_sum )
return right_sum;
else
return cross_sum;
}
}
int
main()
{
int A[] = { 13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7 };
int length = sizeof( A ) / sizeof( int );
int sum = find_max_arr( A, 0, length - 1 );
printf(“max_sum:%d, low:%d, high:%d\n”, sum, last_low, last_high);
getchar();
return 0;
}`
参考资料：《算法导论：第三版》。