最大子序列和

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。例如：

输入: [-2,1,-3,4,-1,2,1,-5,4]

输出: 6

解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

动规非常好理解，难以理解的是一种双指针扫描的解法。记录一下自己的理解。

双指针

双指针解法的共性

双指针是一种剪枝。

问题空间往往很大，而求出题目要求的答案，如最值，往往仅需比较弱的条件，不需要实际搜索完整个问题空间就能得出答案。双指针的精髓在于用 目前已有的信息 推断 问题空间某个子集 内的信息，从而避免搜索这个子集。

比如这道题。

最大子序列和的双指针解法

解法和证明

设置两个指针（数组下标）p、q。闭区间 [p, q] 即为正在考虑的子区间。开始时，p = q = 0。现在移动指针 q，并维护p 到 q 的序列和 sum 、目前为止 sum 的最大值 maxSum。一旦sum < 0，就停下来。

记 $Sum(x, y)$ 表示子区间 $[x,y]$ 的区间和。下面证明： $$ \forall a, b \text{, where } p \leq a \leq b \leq q, Sum(a,b) \leq maxSum $$

因为 $Sum(p,b)=Sum(p,a-1)+Sum(a,b)$ ，因为指针 $q$ 遇到 $Sum(p,q)<0$ 的情况就会停下来，所以可以保证 $Sum(p,a-1)$ 总是大于0的。那么有 $Sum(p,b) > Sum(a,b)$。q扫描过程中能够保证：$Sum(p,b) \leq maxSum$。那么有 $$ Sum(a,b)<maxSum $$

因此，$[p, q]$ 内的任何子区间都被 $maxSum$ 考虑过了，不需要再搜索。

另一方面，是否需要考虑区间 $[x, y]$, where $p \leq x \leq q < y$ 呢？

不需要！根据上面的结论 (带入 $a=x, b=q$ ) 有： $Sum(x, q) < Sum(p, q) < 0$。那么 $$ Sum(x,y) < Sum(q+1,y) $$ 而 $Sum(q+1,y)$ 是后续过程会考虑的，因此不用担心。

总结：[p, q] 内的任何一点作为答案序列起点的情况都不需要再考虑了，那么直接让 p、q都到 q + 1 的位置，就回到了原来的问题。

一点小漏洞

在实际实现中，算法在遇到负数部分和的时候总是要清空已有序列，回到空序列。这会带来一个问题：如果给定序列全都是负数，答案将是空序列！在要求序列非空的题目中，可以判断原序列的最大值，如果最大值小于0，则答案就是这个最大值。

Java代码

class Solution {
    public int maxSubArray(int[] nums) {
        int maxSum = Integer.MIN_VALUE;
        int currentSum = 0;
        int elemMax = Integer.MIN_VALUE;

        for (int i = 0; i < nums.length; ++i) {
            if (nums[i] > elemMax) {
                elemMax = nums[i];
            }
            currentSum += nums[i];
            if (currentSum < 0) {
                currentSum = 0;
            }

            if (currentSum > maxSum) {
                maxSum = currentSum;
            }
        }
        if (elemMax < 0) {
            maxSum = elemMax;
        }
        return maxSum;
    }

    public static void main(String[] args) {
        int[] array = { -2, 1, -3, 4, -1, 2, 1, -5, 4 };
        int result = new Solution().maxSubArray(array);
        System.out.println(result);
    }
}

Last modified on 2020-10-03