简介
有时候，当我们面临一个问题并且感到不知所措的时候，不妨将问题进行适当的转化，这样做往往可以使解决方案浮现．Maximum Subarray 问题（最大子数组之和问题）是这样子的：输入一个非空数组，要求找出该非空数组的一个子区段的和，该子区段同时必须是所有可能找到的子区段当做最大的子区段，一个子区段表示数组中一段连续的范围，即子区段代表着一个或若干个连接着的数组格子，中间不能有间隙．
例如，对于输入
0 1 2 3 4 5 6 7 8
nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
我们可以找到最大子区段是 [3, 6]，即在 nums 数组中，从下标为 3 的元素开始一直到下标为 6 的这4个元素
nums[3..6] = [4, -1, 2, 1]
的和是最大的：
sum(nums[3..6]) = 4 + (-1) + 2 + 1 = 6
其他任意的区段 i, j, 0 <= i <= j <= nums.len 所引用的子数组的和都都不超过 sum(nums[3..6]) = 6，所以最大子区段是 [3, 6]，而这个最大子区段所引用的子数组的和 6 就是我们要返回的答案．具体地，对于非空数组 nums 的一个子区段 [i, j]，我们说它所引用的子数组是
[nums[i], nums[i+1], ..., nums[j]]
即 nums 数组中所有下标大于等于 i 而小于等于 j 的元素（并且保持在原来数组中的次序）．
同样可以看到，nums 的子区段 [0, 2] 所引用的子数组是 [nums[0], nums[1], nums[2]] 也就是 [-2, 1, -3]，它的和为 sum(nums[0..2]) = -2 + 1 + (-3) = -4 < 6，所以说 [0, 2] 不是最大的子区段，sum(nums[0..2]) = -4 自然也就不是我们要的答案．
解法一：穷举
穷举法的存在的意义就是像我们说明：对于任何一个非空且长度有限的数组 nums，Maximum Subarray 问题的答案都总是存在，并且，在足够长且有限长的时间内我们总能找到它．然而，穷举法，除了在少数情况下，一般来说都是较为低效的方法，例如，在这类 Maximum Subarray 问题中，穷举法（逐一不重复地尝试所有可能的 sum(nums[i..j])）的时间复杂度其实是$O(n^2)$的：
public int MaximumSubarrayByBruteForce(int[] nums) {
int maxSum = nums[0];
for (var i = 0; i < nums.Length; i++) {
int currentSum = 0;
for (var j = i; j < nums.Length; j++) {
currentSum = currentSum + nums[j];
if (currentSum > maxSum) {
maxSum = currentSum;
}
}
}
return maxSum;
}
我们用 s(i,j) 表示 nums[i] + nums[i+1] + ... + nums[j]，以上列出来的算法的搜索空间直观地展现出来是这样的：
s(0,0) s(0,1) s(0,2) ... s(0,n)
s(1,1) s(1,2) ... s(1,n)
s(2,2) ... s(2,n)
...
s(n,n)
其中的 n 表示数组的长度即 nums.Length，在最坏的情况下，例如当 s(n,n) 大于所有的 s(i,j) 的时候，该算法将需要遍历完该搜索空间的全部$n(n+1)/2$项，也就是将要从 s(0,0) 开始，一直找到 s(n,n) 才能结束，而在一般情况下，该算法需要检查的搜索空间的元素的个数也在$1$到$n(n+1)/2$之间．不过，该算法没有开辟额外的大小与原数组相当的存储空间（而仅仅是定义了几个变量用于存储中间状态），所以，空间复杂度是$O(1)$．
解法二：寻找累积数组的最大增长区间
我们用 s(i) 表示 nums[0] + nums[2] + ... + nums[i] 也就是原数组 nums 的前 i+1 项和，那么，我们有
s(j) - s(i) = nums[0] + nums[1] + ... nums[j] - (nums[0] + nums[1] + ... + nums[i])
= nums[i+1] + nums[i+1] + ... + nums[j]
= s(i+1, j)
例如：
s(5) = nums[0] + nums[1] + nums[2] + nums[3] + nums[4] + nums[5]
s(2) = nums[0] + nums[1] + nums[2]
s(5) - s(2) = nums[3] + nums[4] + nums[5]
= s(3, 5)
找到这个规律或者说这个关系式又有什么意义呢？这个关系式想表达的其实也就是：非空数组 nums 的第 i+1 项到第 j 项的和恰好等于它的一阶累加数组 snums1 的第 j 项与第 i 项的差．其实这有点类似我们大一的时候学过的牛顿-莱布尼茨定理，它描述了一个黎曼可积函数$f$的定积分和它的一个原函数$F$的函数值的差的关系，其中原函数$F$与被积函数$f$的关系是$F^{\prime}(x) = f(x)$
$$ \int_{a}^{b} f(x) dx = F(b) - F(a) $$
我们刚刚得出的这个结论 s(j) - s(i) = s(i+1, j) 你可以（不严谨地）看做是这个微积分基本公式的离散形式．它的意义就是在于，我们可以把原问题转化为一个新问题：寻找非空数组 nums 的一阶累加数组 snums1 的「最大增长区间」．
那什么又叫做最大增长区间呢？定义如下：设 a 是一个非空数组，a 的长度是 n，[i0, j0] 是关于非空数组 a 的一个*最大增长区间*当且仅当对任意 0 <= i <= j <= n-1 都有 a[j0] - a[i0] >= a[j] - a[i]．这就是最大增长区间的定义．
且来看一下一个例子，输入为
nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
我们的原问题是：寻找 [i, j] 使得和 s(i, j) = nums[i] + nums[i+1] + ... + nums[j] 最大并返回这个和 s(i, j) 的值．原数组的可视化如图１所示．
图１：原数组
对原数组进行一次累加运算（时间复杂度是$O(n)$），我们可以得到原数组 nums 的一阶累加数组 snums1，它是
snums1 = [-2, -1, -4, 0, -1, 1, 2, 7, -3, 1]
你应该知道累加运算是怎么运算的，比如说 snums1 的第一项 snums1[0] = nums[0]，第二项 snums1[1] = nums[0] + nums[1]，第三项 snums[2] = nums[0] + nums[1] + nums[2]，等等以此类推…… 在编程实现中，我们用一个变量保存累加数组前一项的值 snums1[i-1]，这样，在计算 snums1[i] 的时候只需计算 snums1[i] = snums1[i-1] + nums[i] 就可以了，所以说进行一次累加运算的时间复杂度是$O(n)$．那么原数组 nums 的一阶累加数组 snums1 的可视化如图２所示：
图２：原数组的一阶累加数组
看到了吗？我们只需找出图２中的最大增长区间，也就是蓝色线描述的那个范围，我们就可以解出原问题，图２底部蓝色线的右端的函数值是$2$，左端是$-4$，按照一阶累加数组的定义，这个$2-(-4)$（图２）其实就是原数组的$4 + (-1) + 2 + 1$（对比图１），而在图２中，我们显然找不到更大的比这还大的上下波动区间了，所以，答案就是 $4 + (-1) + 2 + 1 = 6$无疑．假如说，原问题问的不是一个固定长度的非空数组的最大子区段的和，而是问的是一个定义在闭区间$[a,b]$上的连续函数$f$的最大定积分$\max \int_{p}^{q} f(x) dx, a \leq p \leq q \leq b$，那么这时你再把图１看做是$f$的图像，图２看做是$f$的某个原函数$F$的图像，就会更加容易理解．
说了这么多，好像只不过是给原问题换了一种表述方式，毕竟我们还是一下子看不出怎么去找这个「最大定积分」，也就是说，哪怕我们看到了图２，虽然似乎是明白了一点，但是这个最大的波动区间从$-4$到$2$具体又是怎么找出的呢？如果说这个寻找一阶累加数组的最大增长区间的算法同样我们只能找到$O(n^2)$的，那这种问题的转化其实没什么意义．但事实上，这种算法不仅存在，而且是$O(n)$的，我们立马就知道原问题可以被以$O(n)$的时间复杂度求解了！因为：对原数组进行一次累加的时间复杂度是$O(n)$，从累加数组中寻找最大增长区间的时间复杂度还是$O(n)$，前面做完一个$O(n)$的操作，后面再做一个$O(n)$的操作，最后总的时间复杂度显然还是$O(n)$.
从一个给定数组中寻找最大增长区间的增幅的算法是这样的：
public int MaxProfit(int[] prices) {
int minprice = int.MaxValue;
int maxprofit = 0;
for (int i = 0; i < prices.Length; i++) {
if (prices[i] < minprice)
minprice = prices[i];
else if (prices[i] - minprice > maxprofit)
maxprofit = prices[i] - minprice;
}
return maxprofit;
}
再一次感谢 LeeCode，题目全，答案也全，讲解也详细，它本来是 Problem #121. Best Time to Buy and Sell Stock 问题的解答（原答案是 Java 的，不过鉴于 Java 和 C# 这么相似，那段代码只改几个字符就可以直接拿来用），不过它恰巧是我们所需要的：返回一个给定数组的最大增长区间的增幅．如代码所示，该算法只需要过一遍输入数组 prices，在这其中，不断地更新 minprice 和 maxprofit，假设 prices 的长度是 n，那么充其量不过进行$2n$次比较，还是很快的！可以看到该算法的时间复杂度是$O(n)$．假如说输入数组是
prices = [-2, -1, -4, 0, -1, 1, 2, 7, -3, 1]
那么它就会找到「买股票的最佳节点」-4，以及「卖股票的最佳节点」2，然后计算出「最大利润」$2-(-4)=6$，这正好就是我们想要的．
整块拼图所有的碎片似乎都已找到，不过，在真正进行整合之前，有几个*特例*需要我们注意：首先，假如说当原数组 nums 的长度是 1 时，如果我们还是按照同样的方法先进行累加，再代入 MaxProfix 函数去算，就会出错，因为原数组的长度是 1，所以原数组的一阶累加数组这时候还是原数组不变，那么给 MaxProfix 函数的输入就是一个长度为 1 的数组 prices，MaxProfit 对于一个长度为 1 的输入，给出的输出显然是 0，因为没有差价，何来「最大利润」？比如说，输入是
nums = [2]
进行累加后是
snums = [2]
再输入 MaxProfit 函数就是
prices = [2]
从 prices 这个数组中我们能看到「买卖股票的最佳时机」吗？看不到，所以 MaxProfit 函数输出 0. 然后 0 是我们要的答案吗？0 是原数组 nums 的最大子数组之和吗？不是的，原数组 nums 的最大子数组之和显然是 2 而不是 0．这时候怎么办呢？是我们的方法一开始就错了吗？也不完全是．要进行改进很简单，我们只需在 MaxProfit 函数的输入数组前面再「插入」一个 0，也就是让这里的 prices 数组变成
prices = [0, 2]
这个时候，「最佳买卖时机」不就是 0 和 2 了吗？「最大利润」不就是 2 了吗？况且，实际上，即使对于长度大于 1 的原数组，prices 数组在 snums 数组前边添上一个 0，也并不影响最终答案的正确性．这就解决了“原输入数组长度为1”的这样一个edge case.
另外，当原数组 nums 的元素全部小于等于 0 的时候，累加数组显然是「只减不增」的，自然，这时候也没有什么「最佳买卖时机」而言，MaxProfit 函数对于一个单调递减数组作为输入，输出自然也是零，例如，考虑原数组
nums = [-1, -2, -3]
进行一次累加运算后得到
snums = [-1, -3, -5]
插入 0 后作为 MaxProfit 函数的输入就是
prices = [0, -1, -3, -5]
有「最佳买卖时机」吗？没有，所以 MaxProfit 函数输出 0，然后，正确答案，据我们所知，在这种snums 只减不增的情况下，应该是原数组的最大值 max(nums)，所以，对于 MaxProfit 函数的返回值，我们需要单独保存，判断它是否等于 0，如果等于 0，那我们就应当返回原数组的最大值 max(nums) 作为答案．
当然，原数组应当被保证是非空的，除了这些之外，就没有什么别的 edge cases 需要再考虑了．
以下为具体C#实现
public class Solution {
public int MaxProfit(int[] prices)
{
int minprice = int.MaxValue;
int maxprofit = 0;
for (int i = 0; i < prices.Length; i++)
{
if (prices[i] < minprice)
minprice = prices[i];
else if (prices[i] - minprice > maxprofit)
maxprofit = prices[i] - minprice;
}
return maxprofit;
}
public int MaxSubArray(int[] nums)
{
int[] nums2 = new int[nums.Length+1];
nums2[0] = 0;
for (var k = 0; k < nums.Length; k++) {
nums2[k+1] = nums[k];
}
if (nums.Length == 1) {
return nums[0];
}
int max = nums[0];
for (var j = 0; j < nums.Length; j++) {
if (nums[j] >= max) {
max = nums[j];
}
}
for (var i = 1; i < nums2.Length; i++) {
nums2[i] = nums2[i] + nums2[i-1];
}
int m = this.MaxProfit(nums2);
if (m == 0) {
return max;
}
return m;
}
}
由于编码水平有限，其实还有很多需要改进的地方．
总结
原来看起来似乎穷举是唯一办法的难题，经过一次简单地累加运算，自然而然地就被转化为寻找最大增长区间增幅的问题，问题得到了简化，解法也变得高效．它山之石可攻玉，或许说的就是这种道理吧．