David Gries 在 1982 年第 2 期的 Science of Computer Programming 第 207 页~第 214 页的“A Note on the Standard Strategy for Developing Loop Invariants and Loops”一文中系统地推导并验证了算法 4。
算法 1 大约对函数 max 进行了 n^3/6 次调用，算法 2 大约进行了 n^2/2 次调用，算法 4 大约进行了 2n 次调用。算法 2b 为累加数组使用了线性的额外空间，算法 3 为栈使用了对数的额外空间。其他算法仅使用了常数的额外空间。算法 4 是实时的：一趟输入完毕它就计算出答案，这特别适用于处理磁盘文件。
绘制随机遍历的累加和。
如果将 cumarr 声明成 float *cumarr 那么赋值 cumarr = realarray + 1 将意味着 cumarr[-1] 指向 realarray[0]。
6. 证明任何计算最大子向量的正确算法都必须检测所有 n 个输入。（有些问题的算法可以正确地忽略某些输入；请思考答案 2.2 中 Saxe 的算法，以及 Boyer 和 Moore 的字串搜索算法。）
7. 当我第一次实现这些算法时，我总是使用脚手架将各种不同算法所产生的答案和算法 4 所产生的答案进行比较。当看到脚手架报告算法 2b 和算法 3 中的错误时，我很烦躁。但是当我仔细研究这些数值答案时，我发现它们尽管不一样，却非常接近。这意味着什么呢？
浮点加法不一定需要关联。
除了计算区域中的最大和之外，返回数组每端最大向量结束的信息。
使用赋值 maxsofar = -∞ 替换 maxsofar = 0。如果 -∞ 的使用让你迷惑，也可以使用 maxsofar = x[0]，为什么？
10. 假设我们想要查找的是总和最接近 0 的子向量，而不是具有最大总和的子向量。你能设计出的最有效的算法是什么？可以应用哪些算法设计技术？如果我们希望查找总和最接近某一给定实数 t 的子向量，结果又将怎样？
初始化累加数组 cum，使得 cum[i]=x[0]+...+x[i]。如果 cum[l-1]=cum[u]，那么子向量 x[l..u] 之和就为 0。因此，可以通过定位 cum 中最接近的两个元素来找出和最接近零的子向量；这可以通过排序数组，在 O(n log n) 时间内完成。这样得到的运行时间不超过最优时间的常数倍，因为任何能够解决这个问题的算法都能够用于解决“元素唯一性”问题（判断数组中是否包含重复元素。Dobkin 和 Lipton 证明“元素唯一性”问题所需的时间跟最坏情况下决策树模型的计算所需的时间差不多）。
11. 收费公路由 n 个收费站之间的 n-1 段公路组成，每一段公路都有相关的使用费。如果在 O(n) 时间内驶过两个收费站，并且仅使用一个费用数组；或在固定时间内驶过两个收费站，并且使用一个具有 O(n^2) 个表项的表，那么给出两站之间的行驶费很容易。请描述一个数据结构，该结构仅需要 O(n^2) 的空间，却可以在固定的时间内完成任意路段的费用计算。
假设收费公路是笔直的，则收费站 i 和收费站 j 之间的总费用为 cum[j]-cum[i-1]，其中 cum 是类似上题的累加数组。
for i = [l, u]
x[i] += v
其中 l、u 和 v 为每次运算的参数（l 和 u 为满足 0 <= l <= u < n 的整数，v 为实数）。完成这 n 次运算之后，x[0..n-1] 中的各个值将按顺序排列。上面刚刚描述的方法需要 O(n^2) 的运行时间。你能给出一个更快的算法吗？
本答案使用另一个累加数组。可以使用赋值语句：
for i = [l, u]
x[i] += v
替代循环
cum[u] += v
cum[l-1] -= v
上面的两个赋值语句先对 x[0..u] 加上 v，然后再从 x[0..l-1] 中减去 v。这些和都计算完毕后，我们用下面的语句计算数组 x：
for (i = n - 1; i >= 0; i--)
x[i] = x[i+1] + cum[i]
这样就把 n 次求和的最坏情况运行时间从 O(n^2) 降到了 O(n)。在 6.1 节描述的 Appel 的 n 体程序中，收集统计数的时候出现了这个问题。使用上述解决方案后，统计函数的运行时间从 4 小时降到了 20 分钟。当程序的执行需要一年时，这样的加速不是很重要；但是如果程序的执行只需要一天，这样的加速就非常重要了。
为了在 O(m^2n) 时间内找出 mn 的数组中总和最大的子数组，可以在长度为 m 的维度上使用算法 2 的方法，在长度为 n 的维度上使用算法 4 的方法。这样就可以在 O(n^3) 时间内解决 n*n 问题，这个结果在长达 20 年的时间内一直是最佳的。在 1998 年的 Symposium on Discrete Algorithms（第 446 页~第 452 页）上，Tamaki 和 Tokuyama 提出了一种稍快一些的算法，运行时间为 O(n^3[(loglogn)/(logn)]^0.5)。他们还给出了一种用于找出总和至少为最大值一半的子数组的 O(n^2logn) 近似算法，并介绍了其在数据挖掘中的应用。最理想的下界仍然正比于 n^2。