求不相交的两个子数组的最大连续和

int32位 posted @ Oct 16, 2013 07:54:10 PM in algorithm , 4080 阅读

转载请注明：http://krystism.is-programmer.com/若有错误，请多多指正，谢谢！

求一个数组的两段连续的部分的最大和，例如1,-2,2,3,-4，结果就是6，第一段就是1，第二段就是2,3。而数组-2,3,-1,2,-5,-6,7,-3,4,-9,2,1，第一段是3,-1,2，第二段是7,-3,4，结果就是12。

这个其实就是数组最大连续和的扩展问题，经典DP问题。求最大连续和并不难，我们只需要遍历数组一次，并用一个dp[i]函数记录从数组开头到第i个元素的子数组的最大和，显然if i == 0, dp[i] = a[0], 而if i > 0, 需要考虑dp[i - 1] 的符号，如果dp[i - 1] <= 0，则dp[i] = a[i]，因为前面i-1个元素最大连续和不大于0, 加上当前元素不可能大于当前元素，只会越加越小, 即小于a[i]。而当dp[i - 1] > 0时， dp[i] = dp[i - 1] + a[i]，原因很简单，前面的连续和大于0, 加上当前元素a[i]，肯定会大于a[i]. 有了这个思路，算法就很简单了。这里时间复杂度是O(n),空间复杂度也是O(n),但我们发现我们只需要一个最大的和，那些前面算出的和，如果不是最大，根本没有必要保存，我们只需维护一个保存当前最大和的变量就可以了，因此空间复杂度可以降低为O(1)。

要求两段连续的部分和的最大值，可以先把数组分成两个各不相交的子数组，然后分别求子数组的最大连续和，相加最大即为所求。

附上代码：

/* coding=UTF-8 */
#include <stdio.h>
#include <limits.h>
#define MAX_LENGTH 1000
#define MAX(a, b) ((a) > (b) ? (a) : (b))
int errno;
/* 求一维数组最大连续和 */
int max_subarray(int *a, int len)
{
	errno = 0;
	if (NULL == a || len < 1) {
		errno = 1;
		return 1;
	}
	int max = a[0], i, sum = a[0];
	for (i = 1; i < len; i++) {
		if (sum < 0) {
			sum = a[i];
		} else {
			sum += a[i];
		}
		max = MAX(max, sum);
	}
	return max;
}
/* 求一个数组的两段连续的部分的最大和
 * 输入一个数组a，以及长度len
 * 思路：先把a分成前后两部分，分别求两部分的最大连续和
 * 依次遍历求得两个子数组的最大连续和最大即为所求
 */
int op(int *a, int len)
{
	errno = 0;
	/* 输入异常处理 */
	if (NULL == a || len < 2) {
		errno = 1;
		return 0;
	}
	int i, max = INT_MIN;
	for (i = 1; i < len; i++) {
		int t1 = max_subarray(a + i, len - i);
		int t2 = max_subarray(a, i);
		max = MAX(max, t1 + t2);
	}
	return max;
}
int main(int argc, char **argv)
{
	int a[] = {1,-2,2,3,-4};
	int b[] = {-1, -1, -1, -1};
	int c[] = {-1, 1};
	printf("%d\n", op(a, 5));
	printf("%d\n", op(b, 4));
	printf("%d\n", op(c, 2));
	return 0;
}

转载请注明：http://krystism.is-programmer.com/若有错误，请多多指正，谢谢！