本章介紹分治法故源，首先通過前兩節(jié)最大子數(shù)組、矩陣乘法兩個問題說明分治法的一般步驟：分解汞贸，解決绳军，合并。當(dāng)子問題需要遞歸求解時稱為遞歸情況矢腻，足夠小可直接得出解為基本情況门驾，其余一些與原問題不同子問題看做合并步驟部分。
然后介紹三種遞歸式的解法：代入法多柑、遞歸樹法和主方法猎唁。

1. 代入法：猜測算法的復(fù)雜度界，用數(shù)學(xué)歸納法證明正確性顷蟆。
2. 遞歸樹法：將遞歸式轉(zhuǎn)換為樹，結(jié)點(diǎn)表示不同層次的遞歸調(diào)用產(chǎn)生的代價腐魂。然后采用邊界和技術(shù)求解帐偎。
3. 主方法：求解如下遞歸式的界

一般忽略遞歸式聲明、求解的技術(shù)細(xì)節(jié)和向下蛔屹、向上取整及邊界條件削樊。

4.1 最大子數(shù)組問題

問題描述：一個記錄每天股票價格的數(shù)組，尋找一段日期兔毒，使得從第一天到最后一天股票價格凈變值最大漫贞。

分析：第一個想法：最低價格買進(jìn)，最高價格賣出時收益最大育叁，但是最高價可能比在最低價更早出現(xiàn)迅脐。那么最低價格買進(jìn)或者最高價格賣出呢？即：

1. 尋找最高和最低價格
2. 從最高價開始向左尋找之前的最低價豪嗽；從最低價開始向右尋找之前的最高價谴蔑。
3. 取兩對價格中差值最大者。

說明有時最大收益既不是在最低價時買進(jìn)龟梦，也不是最高價賣出隐锭。

暴力法：嘗試每對可能的買進(jìn)、賣出的日期組合计贰，Ω(n^2)的復(fù)雜度钦睡。

問題變換

不從每日價格的角度看待輸入，而是考察每日價格變化躁倒，即當(dāng)天和前一天的價格差荞怒。原輸入數(shù)組變?yōu)椋?/p>

使用分治法求解

首先將原問題分解為一些規(guī)模相近的子問題，即將原數(shù)組分兩半分別求解挣输。A 的任何連續(xù)子數(shù)組的位置必然是以下情況：

int a[20] = {0, 13,-3,-25,20,-3,-16,-23,18,20,-7,12,-5,-22,15,-4,7};
struct node
{
    int mxl, mxr, sum;
};
node CrossSum(int a[], int low, int mid, int high)
{
    int i, j, sum, maxl, maxr;
    int leftsum = -INF;
    sum = 0;
    for (i = mid; i >= low; i --)//從中間向前遍歷完丽，故一定選中a[mid]
    {
        sum += a[i];
        if(sum > leftsum)
        {
            leftsum = sum;
            maxl = i;
        }
    }
    int rightsum = -INF;
    sum = 0;
    for (j = mid + 1; j <= high; j ++)//從中間向后遍歷
    {
        sum += a[j];
        if(sum > rightsum)
        {
            rightsum = sum;
            maxr = j;
        }
    }
    node x;
    x.sum = leftsum + rightsum;   //左右最大值之和
    x.mxl = maxl;
    x.mxr = maxr;
    //printf("insub %d %d %d\n", x.mxl, x.mxr, x.sum);
    return x;
}
node FindMaxSub(int a[], int low, int high)
{
    node x, y, z;
    int i , j, mid;
    if (low == high)
    {
        x.mxl = low;
        x.mxr = high;
        x.sum = a[low];
        return x;
    }
    mid = (low + high) / 2;
    //printf("mid = %d\n", mid);
    x = FindMaxSub(a, low, mid);
    y = FindMaxSub(a, mid + 1, high);
    z = CrossSum(a, low, mid, high);
    //printf("l = %d %d %d\n", x.mxl, x.mxr, x.sum);
    //printf("r = %d %d %d\n", y.mxl, y.mxr, y.sum);
    //printf("cro = %d %d %d\n", z.mxl, z.mxr, z.sum);
    if (x.sum >= y.sum && x.sum >= z.sum)
        return x;
    else if (y.sum >= x.sum && y.sum >= z.sum)
        return y;
    else if (z.sum >= y.sum && z.sum >= x.sum)
        return z;
}

分治算法的分析

與歸并排序的一樣，故也為Θ(nlgn)抠璃。

練習(xí)

4.1-1

答：返回A中最大的單個元素max(A[i])

4.1-2

偽代碼：

FIND-MAX-SUBARRAY(A, low, high)
  left = 0
  right = 0
  sum = -∞
  for i = low to high
      current-sum = 0
      for j = i to high
      current-sum += A[j]
      if sum < current-sum
          sum = current-sum
          left = i
          right = j
  return (left, right, sum)

4.1-3

暴力算法C++實(shí)現(xiàn)：

node FindMaxSub(int a[], int low, int high)
{
    int i, j, right = 0, left = 0;
    int sum = -INF;
    for (i = low; i <= high; i ++)
    {
        int curs = 0;
        for ( j = i; j <= high; j++)
        {
            curs += a[j];
            if (sum < curs)
            {
                sum = curs;
                left = i;
                right = j;
            }
        }
    }
    node x;
    x.sum = sum;
    x.mxl = left;
    x.mxr = right;
    return x;
}

暴力法 T(n) = a * n^2, 遞歸法 R(n) = b * nlgn站楚，比較可得交叉點(diǎn)。改后不會變搏嗡，相當(dāng)于合并圖像時取兩段較低的部分窿春。

4.1-4

答：每次返回子數(shù)組之前判斷和是否小于0，若是則返回sum = 0采盒。

4.1-5

答：用動態(tài)規(guī)劃的思想實(shí)現(xiàn)旧乞。若當(dāng)前和小于0則置0重新計(jì)算。C++代碼：

node FindMaxSub(int a[], int low, int high)
{
    int i, j, right = 0, left = 0;
    int sum = -INF, curs = 0;
    for (i = low; i <= high; i ++)
    {
        curs += a[i];
        if (curs > sum)
        {
            sum = curs;
            right = i;
        }
        if (curs < 0)
        {
            curs = 0;
            left = i + 1;
        }
    }
    node x;
    x.sum = sum;
    x.mxl = left;
    x.mxr = right;
    return x;
}

4.2 矩陣乘法的Strassen算法

簡單分治法

第五行分解矩陣若創(chuàng)建12個新矩陣將花費(fèi)Θ(n ^2)左权。通過原矩陣的一組行皮胡、列下標(biāo)指定子矩陣可以不用復(fù)制，故第五行可在Θ(1)內(nèi)實(shí)現(xiàn)赏迟。

• n = 1時 T(1) = Θ(1)

• n > 1時 為遞歸情況屡贺，共8 次遞歸調(diào)用，每次完成兩個n/2 * n/2的子矩陣乘法時間 8T(n/2)， 矩陣加法總時間Θ(n ^2)甩栈⌒合桑總時間

解出來實(shí)際上還是復(fù)雜度 Θ(n ^3)。

Strassen方法

4.3 用代入法求解遞歸式

代入法求解分兩步：

1. 猜測解的形式
2. 用數(shù)學(xué)歸納法求出解中的常數(shù)殴蹄，并證明正確性究抓。

例：確定下式上界

1. 歸納假設(shè)不夠強(qiáng)，無法證出準(zhǔn)確的界時蟋恬，可以試著從先前的猜測減去一個低階項(xiàng)翁潘。
2. 改變變量，函數(shù)整體替換筋现。

練習(xí)

4.3-1

4.3-2

4.3-3

4.4 用遞歸樹解遞歸式

畫出遞歸樹是做出好的猜測的簡單直接方法。在遞歸樹中箱歧，每個結(jié)點(diǎn)代表一個單一子問題的代價矾飞。將樹中每層代價求和，將所有層次代價求和得到遞歸調(diào)用總代價呀邢。

4.5 用主方法求解遞歸式

則不能用，因?yàn)閒(n)并不是多項(xiàng)式意義上的大于价淌，遞歸式在情況2~3之間申眼。

練習(xí)

4.5-1

4.5-2

4.5-4