问题：
设有一个数组 \( a[1],a[2],a[3],\ldots,a[n] \)
求这个数组的最长子数组，这个子数组元素和为 \( 0 \)
例如，对于数组 \( \{1,3,8,-11,0,-7,12\} \)
其和为 \( 0 \) 的最长子数组为 \( \{3,8,-11,0\} \)
方法一：
既然所求的是最大子数组，我们不妨从长往短找，以便减少查找次数
对于数组 \( a[1],a[2],a[3],\ldots,a[n] \)
- 其最长子数组为其本身，所以先计算
$$ a[1]+a[2]+\cdots+a[n] $$
判断其是否为 \( 0 \) - 其次长子数组为 \( a[1],a[2]…,a[n-1] \) 和 \( a[2],a[3]…,a[n] \)
分别计算这两个子数组和 - 依次减少数组长度，直到找到最长子数组
需要注意的是：
- 若找到长为k的最长子数组，不能立刻停止计算
而要继续计算完剩下长度为k的子数组是否和为0，防止最长子数组不唯一 - 分析该种计算方法，在最坏情况下(即最长子数组不存在)，需要的计算步骤为：
$$ 1+2+3+\cdots+n=\Theta(n^2) $$
即时间复杂度是数组长度的平方
这种算法相信是大家都能想到的，思想是“暴力枚举”
那么有没有一种方法可以简化寻找次数呢？
方法二：
对于数组 \( a[1],a[2],\ldots,a[n] \) 我们想到：能不能通过分治的方法简化运算呢？
我们可以将 \( a[1],a[2],\ldots,a[n] \) 分为 \( a[1],a[2],\ldots,a[n/2] \) 和 \( a[n/2+1],\ldots,a[n] \) 两个部分
再分别求两部分的和为 \( 0 \)的最长子数组
再找到我们刻意忽略的跨过 \( a[n/2] \) 和 \( a[n/2+1] \) 的最长和为0子数组
最后取较大者
这种计算方法需要以下步骤：
- 将 \( a[1],a[2],\ldots,a[n] \) 分为 \( a[1],a[2],\ldots,a[n/2] \) 和 \( a[n/2+1],\ldots,a[n] \)
- 找到 \( a[1],a[2],\ldots,a[n/2] \) 和 \( a[n/2+1],\ldots,a[n] \) 的和为 \( 0 \) 的最长子数组
- 找到跨过 \( a[n/2] \) 和 \( a[n/2+1] \) 的最长和为 \( 0 \) 子数组
- 取最大者
注：
- 若 \( n/2 \) 仍较大，可继续把 \( a[1],a[2],\ldots,a[n/2] \) 再分下去
- 事实上，真正需要计算的只有步骤3，即其实只需要计算如何“合并”即(在此不予证明)
该种算法时间复杂度比枚举稍有优化，为 \( \Theta(n\log n) \)
方法3：
还能继续简化计算步骤么？可以的：
如果我们令
$$ S_n=a[1]+a[2]+\cdots+a[n] $$
即
$$\begin{align}
S_1 &= a[1]\\
S_2 &= a[1]+a[2]\\
S_3 &= a[1]+a[2]+a[3]\\
&\cdots
\end{align}$$
那么我们可以得到一个明显的结论：
如果 \( S_i = S_j \) ，那么 \( a[i+1]+a[i+2]+\cdots+a[j] = 0 \)
如：
$$ S_1=1 \quad S_2=5 \quad S_3=8 \quad S_4=1 $$
则 \( a[2]+a[3]+a[4]=0 \)
用这种算法，我们只需要对 \( a[n] \) 的数组进行一次加法运算并记录(甚至不需要记录)相同 \( S_i \)出现的位置
就可以很快的计算出和为 \( 0 \) 的最长子数组
