最大子序列和

例题见 leetcode 53、918

解法解析

最暴力的算法是比较数组所有子数组的大小，通过滑动窗口来实现。该算法的时间复杂度是O(n^3)（子数组数量为n^2，求和的算法复杂度为O(n)）,空间复杂度为O(1)

具体解析见leetcode53: 里面展示了暴力算法、动态规划、分治算法和Kadane算法四种解题思路；

求子区间最大子序列和 - 分治法解题思路

将区间分割成两个区间，求子区间的最大子序和mSum。假如区间[l, r]的中点为m，那子区间分别为[l, m]与[r, m]，可以知道有3种情况：最大子序列和在左区间、右区间、横跨左右区间；结果为max(l.mSum, r.mSum, 横跨的部分)。

如果不求横跨部分的值，这就是一个简单的分治法问题，无限切分即可（参考归并排序写法）。所以我们重点讨论计算横跨的部分：求左区间[l, m]包含右边界m的最大子序和l.rSum（右区间同理）,然后计算左右相加的值l.rSum + r.lSum。

包含右边界的最大子序和存在两种情况：

1. 「右边界最大子序」全在「右子区间」，此时等于求「右子区间」的「右边界最大子序和」m.rSum=r.rSum；
2. 「右边界最大子序」横跨了左右两个子区间，此时「右边界最大子序和」变成了求「右子区间和」和「左子区间」的「右边界最大子序和」；m.rSum = r.totalSum + l.rSum

因此我们在分治的时候，需要求子区间如下内容：

1. 最大子序和mSum;
2. 包含左边界的最大子序列和lSum;
3. 包含右边界的最大子序列和rSum;
4. 区间和totalSum

从而很自然地写出递归算法：

m.totalSum = l.totalSum + r.totalSum;
m.lSum = max(l.lSum, r.lSum + l.totalSum);
m.rSum = max(r.rSum, r.totalSum + l.rSum);

// 最大子序列和为：
m.mSum = max(l.mSum, r.mSum, l.rSum + r.lSum)

复杂度分析

时间复杂度O(n),空间复杂度O(logn);