分治（Divide And Conquer）

• 分治，也就是分而治之。它的一般步驟是

  ①、将原問題分解成若幹個規模較小的子問題（子問題和原問題的結構一樣，隻是規模不一樣）

  ②、子問題又不斷分解成規模更下的子問題，直到不能再分解（直到可以輕易計算出子問題的解）

  ③、利用子問題的解推導出原問題的解

• 是以，分治政策非常适合用遞歸
• 需要注意的是：子問題之間是互相獨立的

  

• 分治的應用：

  ①、快速排序

  ②、歸并排序

  ③、Karatsuba算法（大數乘法）

（1）主定理（Master Theorem）

• 分治政策通常遵守一種通用模式

  ①、解決規模為 n 的問題，分解成 a 個規模為 n/b 的子問題，然後在 O(nd) 時間内将子問題的解合并起來

  ②、算法運作時間為：T(n) = aT(n/b)+ O(nd)，a > 0, b > 1, d ≥ 0

  

• 比如歸并排序的運作時間是：T(n)= 2T(n/2)+ O(n)，a = 2, b = 2, d = 1 ，是以 T(n)= O(nlogn)
• 思考：為什麼有些問題采取分治政策後，性能會有所提升？

（2）練習1 – 最大連續子序列和

• 來源：力扣（LeetCode）53_最大子序和
• 連結：https://leetcode-cn.com/problems/maximum-subarray

• 給定一個長度為 n 的整數序列，求它的最大連續子序列和

  比如 –2、1、–3、4、–1、2、1、–5、4 的最大連續子序列和是 4 + (–1) + 2 + 1 = 6

• 這道題也屬于最大切片問題（最大區段，Greatest Slice）

• 概念區分：

  ①、子串、子數組、子區間必須是連續的

  ②、子序列是可以不連續的

（3）解法1 – 暴力出奇迹

• 窮舉出所有可能的連續子序列，并計算出它們的和，最後取它們中的最大值

public class Main {
    public static void main(String[] args) {
        int[] nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        System.out.println("maxSubarray1："+maxSubarray1(nums));
        System.out.println("maxSubarray2："+maxSubarray2(nums));
    }

    static int maxSubarray1(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        int max = Integer.MIN_VALUE;//-2147483648整型的最小值
        for (int begin = 0; begin < nums.length; begin++) {
            for (int end = begin; end < nums.length; end++) {
                //sum是[begin,end]的和
                int sum = 0;
                for (int i = begin; i <= end; i++) {
                    sum += nums[i];
                }
                max = Math.max(max, sum);
            }
        }
        return max;
    }

    static int maxSubarray2(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        int dp = nums[0];
        int max = dp;
        for (int i = 1; i < nums.length; i++) {
            if (dp > 0) {
                dp += nums[i];
            } else {
                dp = nums[i];
            }
            max = Math.max(max, dp);
        }
        return max;
    }
}
運作結果：
maxSubarray1：6
maxSubarray2：6
           

• 空間複雜度：O(1)，時間複雜度：O(n)

（4）解法1 – 暴力出奇迹 — 優化

• 重複利用前面計算過的結果

static int maxSubarray3(int[] nums) {
    if (nums == null || nums.length == 0) return 0;
    int max = Integer.MIN_VALUE;//-2147483648最小值
    for (int begin = 0; begin < nums.length; begin++) {
        int sum = 0;
        for (int end = begin; end < nums.length; end++) {
            sum += nums[end];
            max = Math.max(max, sum);
        }
    }
    return max;
}
           

• 空間複雜度：O(1)，時間複雜度：O(n)

（5）解法2 – 分治

• 将序列均勻地分割成 2 個子序列

  [begin , end) = [begin，mid) + [mid, end)，mid= (begin+ end) >> 1

• 假設 [begin, end) 的最大連續子序列和是 S[i , j) ，那麼它有 3 種可能

  ①、[i , j) 存在于 [begin, mid) 中，同時 S[i , j) 也是 [begin, mid) 的最大連續子序列和

  ②、[i , j) 存在于 [mid, end) 中，同時 S[i , j) 也是 [mid, end) 的最大連續子序列和

  ③、[i , j) 一部分存在于 [begin, mid) 中，另一部分存在于 [mid, end) 中

  ✓ [i , j) = [i , mid) + [mid, j)

  ✓ S[i , mid) = max { S[k , mid) }，begin≤ k ＜ mid

  ✓ S[mid, j) = max { S[mid, k) }，mid＜ k ≤ end

public class Main {
    public static void main(String[] args) {
        int[] nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        System.out.println("maxSubArray：" + maxSubArray(nums));
    }

    static int maxSubArray(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        return maxSubArray(nums, 0, nums.length);
    }

    /*求解[begin,end)中最大連續子序列的和*/
    static int maxSubArray(int[] nums, int begin, int end) {
        if (end - begin < 2) return nums[begin];

        int mid = (begin + end) >> 1;
        int leftMax = Integer.MIN_VALUE;
        int leftSum = 0;
        for (int i = mid - 1; i >= begin ; i--) {
            leftSum += nums[i];
            leftMax = Math.max(leftMax,leftSum);
        }

        int rightMax = Integer.MIN_VALUE;
        int rightSum = 0;
        for (int i = mid; i < end ; i++) {
            rightSum += nums[i];
            rightMax = Math.max(rightMax,rightSum);
        }

        int max = leftMax + rightMax;
        return Math.max(max,
                Math.max(
                        maxSubArray(nums, begin, mid),
                        maxSubArray(nums, mid, end)
        ));
    }
}
運作結果：
maxSubArray：6
           

• 空間複雜度：O(logn)

• 時間複雜度：O(nlogn)

  ①、跟歸并排序、快速排序一樣

  ②、T(n) = 2T(n/2)+ O(n)

（6）解法2 – 大數乘法

• 2個超大的數（比如2個100位的數），如何進行乘法？

  ①、按照國小時學習的乘法運算，在進行 n 位數之間的相乘時，需要大約進行 n2 次個位數的相乘

  ②、比如計算 36 x 54

  

• 1960 年 Anatolii Alexeevitch Karatsuba 提出了 Karatsuba 算法，提高了大數乘法的效率