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

int32位 posted @ Oct 16, 2013 07:54:10 PM in algorithm , 3949 阅读
转载请注明: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/若有错误,请多多指正,谢谢!
  • 无匹配
  • 无匹配

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter