连续子序列最大和与乘积问题的分析

问题描述

        给定（可能是负的）整数序列A1, A2,...,AN, 寻找（并标识）使Sum(Ak)(k >=i, k <= j)的值最大的序列。如果所有的整数都是负的，那么连续子序列的最大和是零。

　　对应的乘积问题则要求同样求出连续子序列中乘积最大的部分。

　　我们这里针对最大和与最大乘积的问题分别进行讨论。

 

最大和

最简单暴力的解法

        这个问题有一个最简单直接的穷举解决法。我们看问题，既然要求里面最大的连续子序列。那么所有的连续子序列将由哪些组成呢？以数组的第一个元素为例，连续子序列必须是至少包含元素A1,也可能包含从A1到A2...以及从A1到AN。这样就有N种可能。后面的元素也按照这样类似的办法，以该元素开始，包含该元素的单元素数组，两个元素数组...直到包含数组末尾的数组。

        基于上面的分析，我们可以采用一个两重的循环，假设两个循环的循环变量分别为i, j。第一层循环从第一个元素遍历到后面，第二个元素从>=第一个元素的位置开始到最后。这样就可以遍历到所有的点。然后，我们取所有从i到j的连续数组部分和再比较。这样最终就可以得到最大的连续和以及最大子序列的起始与结束点。

具体的实现代码如下：

 

public static int maxSubSum1( int [ ] a )
{
    int maxSum = 0;

    for( int i = 0; i < a.length; i++ )
        for( int j = i; j < a.length; j++ )
        {
            int thisSum = 0;

            for( int k = i; k <= j; k++ )
                thisSum += a[ k ];

            if( thisSum > maxSum )
            {
                maxSum   = thisSum;
                seqStart = i;
                seqEnd   = j;
            }
        }

    return maxSum;
}

 笼统的来说，这种方法有一个3重循环，时间复杂度有O(N^3)。

 

改进

        前面那个最简单暴力的方法虽然看起来能解决问题，但是循环遍历的次数太多了。里面还是有不少可以改进的空间。比如说，每次我们用变量k遍历i到j的时候，都要计算求和。实际上当每次j增加1时，k把前面计算的结果在循环里又计算了一遍。这是完全没必要的，完全可以重复利用前面的计算结果。这样，通过这么一点改进，我们可以得到如下的算法代码：

 

public static int maxSubSum2( int [ ] a )
{
    int maxSum = 0;

    for( int i = 0; i < a.length; i++ )
    {
        int thisSum = 0;
        for( int j = i; j < a.length; j++ )
        {
            thisSum += a[ j ];

            if( thisSum > maxSum )
            {
                maxSum = thisSum;
                seqStart = i;
                seqEnd   = j;
            }
        }
    }

    return maxSum;
}

 

这种方法更进一步的在于，没必要在i和j之间进行遍历，所以时间复杂度为O(N^2)。对于每个外围循环i来说，当内层的循环j走完一遍，则获得了从i开头到j结束的所有子序列中最大的那个。

 

线性算法

        这个问题还是存在着一个线性时间复杂度的解法。需要我们对数组的序列进行进一步的分析。我们在数组中间找到的连续子序列，可能存在和为负的序列。如果需要找到一个最大的子数组的话，肯定该序列不是在最大子序列当中的。我们可以通过反证的方式来证明。

    假设数组A[i...j]，里面的元素和为负。如果A[i....j]在一个最大子序列的数组中间，假定为A[i...k]，k > j。那么既然从i到j这一段是负的，我把这一段去掉剩下的部分完全比我们假定的这个最大子序列还要大。这就和我的假设矛盾了。

    这个假设还有一个限制，就是该数组就是从i开头的。否则有人可能会这么问，如果我A[i...j]这一部分确实是一个负数，但是在A[i]前面是一个很大的正数，使得他们的和为正数。那不就使得我们的结果不成立了么？如果我们是从某个数组的开头i开始的话，就不存在这个情况。

        结合前面的讨论，我们就可以发现一个有意思的事情，就是假设我们从数组的开头A[0]开始，不断的往后面走，每一步判断是否当前和最大，并保存结果。当发现当前字串和为负数的时候，我们可以直接跳过。假设当前的索引为i的话，从0到i这一段的和是负数，可以排除。然后再从当前元素的后面开始找。这样可以得到最终最大子串和以及串的起点和终点。

详细的实现代码如下：

 

public static int maxSubSum3( int [ ] a )
{
    int maxSum = 0;
    int thisSum = 0;

    for( int i = 0, j = 0; j < a.length; j++ )
    {
        thisSum += a[ j ];

        if( thisSum > maxSum )
        {
            maxSum = thisSum;
            seqStart = i;
            seqEnd   = j;
        }
        else if( thisSum < 0 )
        {
            i = j + 1;
            thisSum = 0;
        }
    }

    return maxSum;
}

该方法只需要遍历数组一遍，通过跳过这些中间和为负的结果。算法时间复杂度为O(N).

 

乘积问题

　　因为要求一个数组里连续子元素乘积的最大值。从初步的思路来说，可能会有这么一个初步的思路。一个数组里可能含有正数，负数，零这几个。对于包含零在内的元素乘积来说，肯定就是０了，这种情况比较特殊。作为最大元素乘积的话，应该尽量考虑取避免包含０，除非所有的乘积都是负数。而对于那些不包含零的序列来说，最大的序列可能为所有正数的乘积，也可能包含有若干个负数。因为负负得正，只要包含有偶数个负数也可能称为最大值。

　　按照刚才的初步讨论，我们可以得到一个比较简单直观的方法。

 

划分法

　　在前面的讨论，我们知道，最大连续乘积更可能出现在不包含零的序列里。所以我们完全可以以零作为隔断点，讲整个数组划分成若干个子段。这样，整个数组的连续最大乘积要么出现在这若干个子段里，要么就是零。

　　如图中所示，我们要做的就是首先找到里面所有的零，将它们作为分割点，然后再去每个分割段里找里面的最大连续乘积。对于这些字段来说，它们不会包含有零，仅可能为若干个正负数的组合。一种求里面所有连续字段最大乘积的办法就是通过两轮循环去遍历所有的可能，然后保存这个子段里最大的值。按照这种思路，实现的代码如下：

public int maxInSegment(int[] a, int l, int r) {
    int max = 0;
    int product = 1;
    for(int i = l; i <= r; i++) {
        product = 1;
        for(int j = i; j <= r; j++) {
            product *= a[j];
            if(product > max)
              max = product;
        }
    }

    return product;
}

   　这部分代码因为有一个两重遍历，它的时间复杂度为O(N^2)。能解决这个问题，只是不算效率很高。

 　　前面取零，并记录它们所在位置的实现可以通过一个LinkedList，每次碰到一个零就将零所在的索引加入到里面。以后每次遍历这个列表，将前后两个元素间的元素作为maxInSegment方法的参数传入来调用取得最大乘积。这部分的代码并不复杂，就不详述了。

　　这种划分的方法虽然解决了问题，但是效率并不高。问题的关键点在于每次得到一个子段的时候，我们是通过蛮力取遍历所有的可能来求最大值。假设我们有一个子段a[i..k]是最大子段中间的一部分，在前面的某一次循环中已经计算过了，可是在后面的循环中还是会计算一遍，这样就浪费了不少时间。如果在这方面有所改进的话，后面的方法应该可以更好。

　　那么，我们还又没有别的办法呢？

 

递推归纳法

　　这里还有一种思考问题的思路。既然我们要求一个数组里连续子序列的最大乘积，那么对于一个数组，假设a[i..j]来说，它的最大连续乘积可能是如下图这样的一个形式：

    这里面的最大值是一个以下标k为结尾的连续子序列。从全局的角度来看，很明显，最终的这个最大连续乘积必然是一个包含某个元素为结尾的子串。只是这儿最大的子串不一定就是从数组的第一个元素作为开头。假如我们从数组开头i到结尾j的范围，求出到所有元素为结尾的子序列最大值，取其中最大的那个，这不就是我们所要求的那个最大连续子序列乘积吗？

　　前面的这个问题概括起来不就是max(a) = max(max(a, i, i), max(a, i, i+1), ...,max(a, i, j)) 这样的一个等式吗？我们这里max(a, i, j)表示从数组i开始到j结束的范围内，包含j作为结尾的最大连续子序列乘积。

　　如果我们需要定义一个递归的关系，在这个问题里，有可能的是max(a, i, k)，它表示的是从i到k的范围内，包含k的一个连续子序列乘积。那么对于它后面的max(a, i, k+1)来说，它们会是一个什么关系呢？它们的递推关系可能会满足如下的几种情况：

１．max(a, i, k)和a[k+1]都是正数且max(a, i, k) * a[k+1] > max(a, i, k)

    在这种情况下，我们取得max(a, i, k) * a[k+1]作为max(a, i, k+1)的值。

２.  max(a, i, k)一个为正，一个为负

　　在这种情况下，后面的元素a[k+1]因为已经是负数，如果和前面的max(a, i, k)相乘的话，得到的值会更小。而且，因为max(a, i, k+1)必须要包含a[k+1]在内，所以最大的这个值就是a[k+1]元素本身。同样，如果前面max(a, i, k)为负，a[k+1]为正，也是一样的结果。

３．max(a, i, k)为正，a[k+1]为负，不过max(a, i, k)之前相连的序列里有负数，比如：

    这个时候，我们会发现a[k+1] * max(a, i, k)不一定是最大的值。在这个示例中，如果再乘上前面的-2得到的结果才是最后最大的。而前面包含-2的这个序列，必然是一个前面序列里的最小值。同样，如果前面的序列里max(a, i, k)是负数，而且a[k+1]也是负数，则它们的直接乘积就是最大值。

　　概括起来就是说包含第k+1个元素为结尾的序列最大乘积应该取自上述三种情况之一：

max(k+1) = max(maxk * a[k+1], mink * a[k+1], a[k+1])。

　　按照同样的道理，我们求得的包含k+1在内结尾的最小乘积序列为：

min(k+1) = min(mink * a[k+1], maxk * a[k+1], a[k+1])

    这样，在求后面整个数组序列里的最大连续乘积的时候，就需要求出包含每个元素为结尾的序列里最大乘积值，然后通过逐步的比较求出最大的那个。详细实现的代码如下：

 

public static int maxProduct(int[] a) {
        int maxCur = 1;
        int minCur = 1;
        int maxTmp = maxCur;
        int minTmp = minCur;
        int result = 0;
        for(int i = 0; i < a.length; i++) {
            maxTmp = Math.max(a[i], Math.max(maxCur * a[i], minCur * a[i]));
            minTmp = Math.min(a[i], Math.min(maxCur * a[i], minCur * a[i]));
            maxCur = maxTmp;
            minCur = minTmp;
            result = Math.max(result, maxCur);
        }

        return result;
    }

 

 

总结分析

        这是一个比较有意思的问题。以前和朋友们曾经讨论过。当然，是在没看过书上的那么多分析之后自己也想到了一个近似O(N)的解法。当时还利用了一种情形，将所有为相邻为正的元素以及为负的元素分别累加起来构成一个新的数组。因为如果要达到最大的子数组，要么就要覆盖所有相邻的正整数，要么会包含一段相邻的负整数子序列。然后形成一个正负数相间的数组。这样再利用前面的线性算法特性进行比较。虽然不如前面的好，但是这是自己思考的结果，总是有价值的。

        另外，在某些情况下会出现上述问题的一个变种，就是假设我们需要支持负数的情况。最坏的情况就是所有元素都是负的，那么就相当于在里面找到最大的那个元素。我们的代码就需要稍微做一点修改。至于怎么改，如果你看明白了分析和代码的话，你懂的:)

        还有一个需要说明一点的就是，在实现的代码中用到了seqStart和seqEnd两个变量。可以将这两个元素定义为类的static变量。这样就构成一个完整的程序了。

 　　对于乘积问题来说，它的递归方法的一个要点是要根据以某个元素为结尾的序列和它后面相邻元素为结尾的连续序列的关系推导。max(k+1) = max(max(k)* a[k+1], min(k) * a[k+1], a[k+1])。只要这个关系能推导出来就好办。当然难也就难在怎么推导出这么个关系来。

 

参考资料

Data structures and problem solving using java