分治法的简单介绍和实现

一、介绍

分治法可以通俗的解释为：把一片领土分解，分解为若干块小部分，然后一块块地占领征服，被分解的可以是不同的政治派别或是其他什么，然后让他们彼此异化。

分治法的精髓：

• 分--将问题分解为规模更小的子问题；
• 治--将这些规模更小的子问题逐个击破；
• 合--将已解决的子问题合并，最终得出“母”问题的解；

二、步骤

• 分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题；
• 解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题；
• 合并：将各个子问题的解合并为原问题的解。

三、应用

给定数组，求数组中的最大值

思路：将数组分为若干个子集，求出最小规模子集内的最大值，然后各个子集之间求最大值，这样子集逐渐变大合并，最后得出答案。

    public static int getMax(int[] nums, int left, int right){
        if(left == right){
        //此处为规模最小子集，直接求解
            return nums[left];
        }

        //此处为递归求解子问题
        int center = (left + right)/2;
        int leftMax = getMax(nums, left, center);
        int rightMax = getMax(nums, center + 1, right);
        //子问题结果合并并返回给上一层
        return leftMax > rightMax ? leftMax : rightMax;
    }