Problem 1 (教材习题 4.1-4)

假定修改最大子数组问题的定义，允许结果为空数组，其和为 $0$ 。你应该如何修改现有算法，使它们能允许空数组为最终结果？

Solution

算法描述如下：

• 首先，对于输入数组作一次线性扫描，看看它是否包含正数。

• 如果全都是负数，则算法返回空数组，其和为 $0$ ，并终止算法。

• 否则，正常运行现有的寻找最大子数组的算法即可。

Problem 2 (教材习题 4.1-5)

使用如下思想为最大子数组问题设计一个非递归的、线性时间的算法。从数组的左边界开始，由左至右处理，记录到目前为止已经处理过的最大子数组。若已知 $A[1..j]$ 的最大子数组，基于如下性质将解扩展为 $A[1..j+1]$ 的最大子数组： $A[1..j+1]$ 的最大子数组要么是 $A[1..j]$ 的最大子数组，要么是某个子数组 $A[i..j+1] (1\le i\le j+1)$ 。在已知 $A[1..j]$ 的最大子数组的情况下，可以在线性时间内找出形如 $A[i..j+1]$ 的最大子数组。

Solution

算法伪代码如下：

从第 5 到 15 行的 for 循环不难看出，该算法的运行时间为 $\Theta(n)$ ，这是一个线性时间的算法。

下面使用 循环不变式 来证明该算法的正确性，第 5 到 15 行的 for 循环的不变式为：每次循环开始前， $A[p..q]$ 是 $A[1..j-1]$ 的最大子数组， $A[i..j-1]$ 是 $A[1..j - 1]$ 的最大后缀子数组。

• 初始化：在第一次迭代开始前，$p = q = i = 1, j = 2$ ，$A[1]$ 显然是 $A[1]$ 的最大子数组和最大后缀子数组，不变式显然成立。

• 保持：若迭代开始前，$A[p..q]$ 是 $A[1..j-1]$ 的最大子数组， $A[i..j-1]$ 是 $A[1..j-1]$ 的最大后缀子数组，

  • 算法第 6 到 11 行使得 $A[i..j]$ 是 $A[1..j]$ 的最大后缀子数组。

    • 因为 $A[1..j]$ 所有的后缀子数组都包含 $A[j]$ ，我们只需要让 $A[k..j-1]$（即 $A[1..j]$ 后缀子数组中不含最后一个元素的部分） 的部分尽可能大（非负的就要最大，负的直接不要——相当于0）就行。

    • 如果 $A[1..j-1]$ 的最大后缀子数组是负的，那么 $A[1..j]$ 的最大后缀子数组就是 $A[j]$ （算法第 6 到 8 行）；

    • 如果 $A[1..j-1]$ 的最大后缀子数组 $A[i..j-1]$ 是非负的，那么 $A[1..j]$ 的最大后缀子数组就是 $A[i..j]$ （算法第 9 到 11 行）；

  • 算法第 12 到 14 行使得 $A[p..q]$ 是 $A[1..j]$ 的最大子数组。

    • $A[1..j]$ 的最大子数组是 $A[1..j-1]$ 的最大子数组和 $A[1..j]$ 的最大后缀子数组中较大的那一个（算法第 12 到 14 行）；

    • 因为 $A[1..j]$ 的最大子数组要么不含 $A[j]$ ，即上述的前一种情况；要么包含 $A[j]$ ，即上述的后一种情况，故而两种情况取最大即可。

  于是，下一次迭代开始前，$A[p..q]$ 是 $A[1..j]$ 的最大子数组， $A[i..j]$ 是 $A[1..j]$ 的最大后缀子数组。循环保持了不变式。

• 终止：最后一次迭代结束后， $j = n + 1$ ，根据循环不变式， $A[p, q]$ 是 $A[1..n+1-1] = A[1..n]$ 的最大子数组。因此，算法 1 是正确的。

补充本题的洛谷模版题链接，读者可以自行编程并提交评测。

Problem 3 (教材习题 4.2-2)

为 Strassen 算法编写伪代码。

Solution

Problem 4 (教材习题 4.2-6)

用 Strassen 算法作为子过程来进行一个 $kn\times n$ 矩阵和一个 $n \times kn$ 矩阵的乘法，最快需要花费多长时间？ 对于两个输入矩阵规模互换的情况，回答相同的问题。

Solution

考虑分块矩阵的乘法。记

$A = \left[\begin{matrix}A_1 \ A_2 \ \vdots \ A_k\end{matrix}\right],$
B = \left[\begin{matrix}B_1 & B_2 & \ldots & B_k\end{matrix}\right]

其中， $A_i$ 和 $B_j$ 都是 $n \times n$ 的矩阵。

$A \cdot B = \left[\begin{matrix}A_1B_1 & A_1B_2 & \ldots & A_1B_k\$
A_2B_1 & A_2B_2 & \ldots & A_2B_k\
\vdots & \vdots & \ddots & \vdots\
A_kB_1 & A_kB_2 & \ldots & A_kB_k\
\end{matrix}\right],
B \cdot A = \left[\sum_{i = 1}^{k} A_iB_i\right]

其中，每次乘法需要 $\Theta(n^{\log 7})$ （Strassen 算法），每次加法需要 $\Theta(n^2)$ （平凡算法）。

所以不难看出 $A\cdot B$ 的运行时间为 $\Theta(k^2 n^{\log 7})$ ，$B\cdot A$ 的时间为 $\Theta(k n^{\log 7})$ 。

Problem 5 (教材习题 4.2-7)

设计算法，仅使用三次实数乘法即可完成复数 $a + bi$ 和 $c + di$ 相乘。算法需接收 $a, b, c, d$ 作为输入，分别生成实部 $ac - bd$ 和虚部 $ad + bc$ 。

Solution

考虑如下两个等式：

$ac - bd = ac + bc - bc - bd = (a+b)c - b(c+d)\$
ad + bc = ad - bd + bd + bc = (a-b)d + b(c+d)

我们只需要计算三次乘积 $P_1 = (a+b)c, P_2 = b(c+d), P_3 = (a-b)d$ 即可分别生成实部 $ac-bd = P_1 - P_2$ 和虚部 $ad+bc = P_2 + P_3$ 。