关于最大子序列和问题以及相关衍生问题的分析

最近在看《数据结构与算法分析》, 里面有提到最大子序列和问题, 也就是从一组N个数中找出其中和最大的连续序列.

书中给出了四种解法, 我感觉确实也是一般寻找解题思路的基本历程, 所以这里准备逐一列出.

O(N^3)解法

这种解法的三层循环依次是 :

从第一个数到最后一个数.
序列中数的数量从1个到N个.
算序列和的时候使用循环求和.

给出缩略代码进行 :

int maxSum = 0;
for(int i = 0; i < N; ++i){
    for(int j = 1; j <= N - i; ++j){
        int curSum = 0;
        for(int k = 0; k < j; ++k){
            curSum += array[i + k];
        }
        if(curSum > maxSum){
            maxSum = curSum;
        }
    }
}

O(N^2)解法

仔细分析上面的算法就可以发现, 其实最后一层循环是多余的, 算法的优化过程, 很多时候就是减少重复计算, 这里很容易看出, 比如我们要计算从array[m] 到 array[n]的序列和, 我们就可以利用array[m] 到 array[n-1]的序列和, 而不是重新从array[m]开始计算, 所以我们可以改进上面的算法 :

int maxSum = 0;
for(int i = 0; i < N; ++i){
    int curSum = 0;
    for(int j = 0; i +　j < N; ++j){
        curSum += array[i　＋ j];
        if(curSum > maxSum){
            maxSum = curSum;
        }
    }
}

O(N)解法

其实优化到O(N^2)再想继续优化的话, 就需要对问题有更深层的理解了. 这里所谓的深层理解, 其实就是一句话 :　最优序列的开头不可能是负数(所以的元素全是负数除外). 这句话再引申一下就是, 最优序列的开头任意多个元素也不可能是负数, 利用这条性质, 当我们发现从某个数开始当前序列和为负时, 可以直接放弃这一列数字, 从下一个数字开始计算, 因为这列数字已经不可能作为最有序列的开头了. 利用这种思路, 我们只需要遍历一遍数组就能够得出答案, 而且在任何时候算法都对它已经读入的数据给出了最佳的答案, 这也就是所谓的联机算法, 该解法实际代码更加简单 :

int maxSum = array[0];  // 这样可以防止所有的元素都是负数
int curSum = 0;
for(int i = 0; i < N; ++i){
    curSum += array[i];
    if(curSum >　maxSum)｛
        maxSum = curSum;
    ｝
    if(curSum < 0){
        curSum = 0;
    }
}

O(NlogN)解法

这种解法速度不如上一种, 却是从一种完全不同的思路, 它体现了一种分治的思想. 这个算法其实也是出于对最有序列的分析而实现的, 分析最优序列的位置分布可知, 最有序列要么在整个数组的左半个部分, 要么在右半个部分, 要么跨越左右. 所以我们只要分别得出位于左半部分序列的最优解, 位于右半部分的最优解, 还有包括左半部分右边界的序列的最优解以及包括右半部分左边界的序列的最优解即可得出答案.

int MaxSubSum(const int* array, int left, int right) {
	int maxLeftSum, maxRightSum;
	int maxLeftBorderSum, maxRightBorderSum;
	int leftBorderSum, rightBorderSum;
	int center = (left + right) / 2, i;
	if (left == right) { return array[left]; }

	maxLeftSum = MaxSubSum(array, 0, center);
	maxRightSum = MaxSubSum(array, center + 1, right);

	maxLeftBorderSum = leftBorderSum = 0;
	for (int i = 0; i <= center; ++i) {
		leftBorderSum += array[i];
		if (leftBorderSum > maxLeftBorderSum) {
			maxLeftBorderSum = leftBorderSum;
		}
	}

	maxRightBorderSum = rightBorderSum = 0;
	for (int i = center + 1; i <= right; ++i) {
		rightBorderSum += array[i];
		if (rightBorderSum > maxRightBorderSum) {
			maxRightBorderSum = rightBorderSum;
		}
	}

	int sum = maxLeftBorderSum + maxRightBorderSum;
	int bigger = maxLeftSum > maxRightSum ? maxLeftSum : maxRightSum;
	return bigger > sum ? bigger : sum;
}

衍生问题1

关于最大子序列求和问题已经完结了, 但是在习题中又出现了新的衍生问题, 求最小正子序列和.

说实话我绞尽脑汁只想到了O(N^2), 也就是bf解法, 没办法搞算法我的智商确实不太够用. 在网上搜索发现了确实存在O(NlogN)的解法.

该解法的关键在于, 假设sum[m]表示序列前m个元素的和, 那么任何一段子序列都可以用sum[x] - sum[y]来表示. 我们要求解最小正子序列和, 只需要找到最相邻的两个sum[i]之间的差, 也就是我们首先遍历数组, 求出sum[i]中 i 从 1 到 N 的所有结果, 然后排序, 然后再相邻相减, 找出最小即可. 代码比较简单就不写了.

衍生问题2

最后还有一个求最大序列乘积.
这个可以用动态规划做, 具体的思路网上很容易找到, 这里暂且不表. 下面是半伪代码 :

int MaxProducts(int* array, size_t size) {
	int curMax = array[0];
	int curMin = array[0];
	int tempMax;
	int tempMin;

	for (int i = 1; i < size; ++i) {
		tempMax = curMax * array[i];
		tempMin = curMin * array[i];

		curMax = max(array[i], tempMax, tempMin);
		curMin = min(array[i], tempMax, tempMin);
	}

	return curMax;
}