1. 前言
首先解释一下这个标题。
最近看了一个关于密室的系列电影，共有三部，个人只觉得第一部比价好看(ps:第三部还没有看)，它有两个名字，一个叫《心慌方》，比较文艺；两一个也叫《心慌方》，当然不可能了，其实是《异次元杀阵》，这个听上去比较科技感强一点。
最大子段和，也叫最大连续子数列和,AC圈都是这么叫的吧。我个人喜欢前面一个。最近也是看到有博主也写关于这个问题的算法，所以自己也想提笔试着写写(非喜勿喷)。关于最大连续子数列和的解释可以看 维基百科。
为什么把两者扯到一起，因为我下面要讲的是解决这个问题的过程，如何演化！
2. 坐标
最容易想到的方法就是枚举，所以的情况都枚举出来，比较一下大小就可以了。
以数组
A = [-2, 11, -4, 13, -5, -2]
为例。
关于如何枚举，我个人容易想到的是2种；
(1) 按子序列的长度枚举
(2) 按子序列的起点、终点枚举
二者其实是一样的，知道起始点就知道长度了，只是第二种记录起始点听上去顺理成章一点。本质上时间复杂度都是O(n^3)
解法1
var A = [-2, 11, -4, 13, -5, -2];
var ans = A[0];
var s;
for(var n = 1; n <= A.length; n++) {
for(var i = 0; i < A.length; i++) {
s = 0;
for(var j = 0; j < n; j++) {
s += A[i+j];
}
if (s > ans) {
ans = s;
}
}
}
console.log(ans, '=========');
解法2
var A = [-2, 11, -4, 13, -5, -2];
var ans = A[0];
var s;
for(var i = 0; i < A.length; i++) {
for(var j = i; j < A.length; j++) {
s = 0;
for(var k = i; k <= j ; k++) {
s += A[k];
}
if (s > ans) {
ans = s;
}
}
}
console.log(ans, '=========');
两中方法其实都是通过记录起始点的手段来来解决问题，也就是记录坐标，有点像《心慌方》中理科女，通过坐标来辨识安全的房间.
(在更新 ans 的时候，可以记录相应的起始点，就得到我们想要的坐标了)
两种枚举的方法都其实是引入了两个变量，在解决很多数学问题上，一些问题通过消元和降次基本上可以解决了。
这种思路也适用于算法设计。
此外，计算机很多的问题都是量导致的，如果量很小的话，问题很容易解决。
仔细观察 解法2 可以发现，我们很多次循环都是在求解 A[i…j] 的累加和，如何避免这种重复的劳动了，
在计算机上面，可以使用另外一种优化手段，空间换时间 ，当然也存在 时间换空间 的
由此可以引申出 3 种优化思路：
(1) 空间换时间
(2) 通过降”量” 来优化这个问题的解(计算机)
(3) 通过 “消元” 或者 “降次” 来优化这个问题的解(数学)
3. 备忘录
解法2 中多次求解 A[i…j] 的累加和，如果能够花费一些空间把它记录下来，不就是省掉一层循环了，降低了时间复杂度；
实际上很多问题都可以通过备忘录，来省去重复的工作。
如果用 sum[i] 表示 A 中 A[0] 到 A[i] 的累加和，那么 A[i..j] = sum[j] - sum[i-1];
我们在外层计算出数组 sum，记录下来，在需要用到 A[i…j] 的时候，通过简单的减法运算就可以实现了，减少了一层循环，时间复杂度就降低到 O(n^2)
var A = [-2, 11, -4, 13, -5, -2];
var sum = [];
sum[0] = A[0];
var ans = A[0];
var s;
for(var i = 1; i < A.length; i++) {
sum[i] = sum[i-1] + A[i];
}
for(i = 1; i < A.length; i++) {
for(var j = i; j < A.length; j++) {
s = sum[j] - sum[i-1];
if (s > ans) {
ans = s;
}
}
}
console.log(ans, '=========');
4. 降 “量”
尝试了第一种优化方式，确实得到了一些优化，那继续尝试第二种咯。
一般在很多问题的处理上，都是通过降 “量” 来优化，比如预先排除一些没有用的数据，来降低数据的量级。而我们这个问题是没有办法 直接通过预先处理、筛选一些数据解决的。
但是最大子段和问题，我们可以换一种方式来理解降 “量”。
如果整个序列只有 1 个或者 2 个元素，问题是不是简单很多。我们解决只有 1 个元素的序列的最大子段和问题，那么就可以解决只有 2 个 元素的最大子段和，进而 4 个、8 个，……
是不是突然感觉有点熟悉，分治 感觉已经呼之欲出了。对，就是 分而治之
求解整个序列的最大子段和，我们可以分解成两部分:
求左半部分的最大子段和，
求右半部分的最大子段和，
根据左、右两个半部分的最大子段和，求解整个序列的最大子段
求解左、右半部分的最大字段和最后都可以分解成 “只有 1 个元素的序列的最大子段和问题”，这大概就是一个小目标.
那么 “只有 2 个元素的序列的最大子段和问题” 可以通过上面的小目标来实现。如果左半部分的最大子段和是 0，那整个序列的最大子段和就在右半部分；如果右半部分的最大子段和是 0，那整个序列的最大子段和就在左半部分；(如果左右都为 0，上述那个如果都满足，依旧是 0)
剩余的情况就是整个序列的最大子段和由 左半部分的最大子段和 和 右半部分的最大字段和 共同组成。
这其实就是分治问题的核心，如何由小的问题汇总大的问题，怎么由先赚它一个亿到成为首富的问题。
具体问题具体分析，最大子段和，也叫最大连续子数列和。关键词是连续。 于是这个问题就是最大连续子序列和要么出现在数组左半部分，要么出现在数组右半部分，要么横跨左右两半部分。横跨左右两半部分就受到连续这个关键词的限制。
具体解法
var A = [-2, 11, -4, 13, -5, -2];
function MaxSubSequence(left, right) {
if (left > right) {
return 0;
}
// 只有 1 个元素的序列
if (left === right) {
return A[left];
}
// 划分为 “左半部分的最大子段和” 和 "右半部分的最大子段和"
var mid = (left + right) / 2;
mid >>>= 0;
var leftMaxSubSequence = MaxSubSequence(left, mid);
var rightMaxSubSequence = MaxSubSequence(mid + 1, right);
// 求横跨左右的最大连续子序列左半部分
var lmax = A[mid], lsum = 0;
for(var i = mid; i >= left; i--) {
lsum += A[i];
if (lsum > lmax) {
lmax = lsum;
}
}
// 求横跨左右的最大连续子序列右半部分
var rmax = A[mid + 1], rsum = 0;
for(var j = mid + 1; j <= right; j++) {
rsum += A[j];
if (rsum > rmax) {
rmax = rsum;
}
}
return Math.max(lmax + rmax, leftMaxSubSequence, rightMaxSubSequence); //返回三者最大值
}
var ans = MaxSubSequence(0, A.length - 1);
console.log(ans, '===============');
整个解法的时间复杂度是 O(n*lgn)
其实我们，可以看到解决这个问题的过程中，我们实际上还是依赖于两个变量，left 和 right，并没有消元
接下来，我们试试消元吧。
5. 消元
前面的两种优化手段依旧和坐标有关系，还是二元，我们尝试一下消元。
一直停留在最大连续子数列和起点和终点上，一直不能愉快地消元，实际这个问题，不管原序列有多少个元素，都有起点和终点，但是
如果只有 1 个元素的话，是不是起点和终点重合，如果原序列很长，就是终点很远，但是起点还是起点，不管原序列多长，变化一直是终点，
所以可不可以不关心起点，只 care 我们的终点，把起点这个元消除掉。
ok，于是我们假设 max[j] 是 序列 A[0…j] 的最大字段和。能不能通过类似数学归纳法来求得一个递推公式呢？！
我们需要解决的就是如何从 max[j] 求出 max[j+1] 的值。
最大连续子数列和，其中关键就是连续。 从 max[j] 到 max[j+1] ，考虑连续与否就可以了。
a. max[j] 的终点是 A[j] b. max[j] 的终点不是 A[j]
a. max[j] 的终点是 A[j]
那么 max[j+1] = Max(max[j-1], max[j-1] + A[j])
b. max[j] 的终点不是 A[j]
假设 max[j] 的终点是 A[m] 那么 max[j+1] = Max(max[j-1], max[j-1] + (A[m+1] + A[m+2] + … + A[j]) )
综上，在递推的过程中我们记录终点 m 就可以了.
所以在遍历的 j 的时候，记录更新 m 就可以了。而记录终点 m 也是为了求 (A[m+1] + A[m+2] + … + A[j])， tmp 记录 A[m+1] 到 A[j-1] 的累积和
如果 tmp + A[j] + max[j-1] > max[j-1] ，max[j] = max[j-1] + tmp + A[j], tmp 也相应地更新为 0； 如果 tmp + A[j] + max[j-1] <= max[j-1] ，max[j] = max[j-1], tmp 也相应地更新为 tmp + A[j]；
具体解法
var A = [-2, 11, -4, 13, -5, -2];
var ans = A[0];
var tmp = 0; // 记录 A[m+1] + A[m+2] + ... + A[j-1]
for(var j = 0; j < A.length; j++) {
if (tmp > 0) {
tmp += A[j]
} else {
tmp = A[j]
}
if (tmp > ans) {
ans = tmp
}
}
console.log(ans, '=========');
该解法的时间复杂度为 O(n)
6. 降维
降维，通过低维打击高维，才是王道。上面的 O(n) 算法中，max[] 只需要 max[j] 和 max[j-1]，所以可以用一个变量 ans 即可解决问题。 在很多动态规划的算法中，可以通过降维来实现空间复杂度的优化， 例如 dp[i][j] = Max(dp[i-1][j], dp[i][j-1]) 之类的， 数组 dp[][] 只用到了 dp[i-1] 和 dp[i]，我们完全可以通过 dpmin[] 来取代 dp[][]，优化空间复杂度。
还有一些动态规划的问题中，例如 dp[i][j] = Max(∑dp[i-1][n](0<=n<j)*A[i][j], A[i][j]) 之类的， dp[i] 的状态与整个 dp[i-1] 数组都有关系的时候， 我们也可以用过 b[j] = Max(∑a[n](0<=n<j)*A[i][j], A[i][j]); a[] = b[]，a[] 和 b[] 做一个交换来优化空间复杂度，当然这样每次交换也牺牲了一部分的效率。
扩展
文章提到的一些解法和优化方法，实际上被大神设计出来，掌握这些最本质的东西，在解决实际问题的时候，有一个渐进式思维，擅用算法，逐步优化，我觉得才是异次元方阵的破解之法。
如果您感兴趣的话，也可以去了解动态规划，分治，备忘录，最大连续子矩阵和 等。我后续也会慢慢去介绍相关的东西。