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

int32位 posted @ Oct 16, 2013 07:54:10 PM in algorithm , 4478 阅读
转载请注明：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/若有错误，请多多指正，谢谢！
  • 无匹配
  • 无匹配
Small_feed 评论 (12)
2
[回复]
Clay Lowe 说:
2025年3月17日 02:12

I should assert barely that its astounding! The blog is informational also always fabricate amazing entitys. Kissimmee Exterminator

3
[回复]
Clay Lowe 说:
2025年3月17日 02:14

Very interesting information, worth recommending. However, I recommend this:  Bed Bug Treatment Orlando

4
[回复]
Clay Lowe 说:
2025年3月17日 02:17

Acknowledges for paper such a beneficial composition, I stumbled beside your blog besides decipher a limited announce. I want your technique of inscription... Oviedo Termite Control

5
[回复]
Clay Lowe 说:
2025年3月17日 02:19

Cool you inscribe, the info is really salubrious further fascinating, I'll give you a connect to my scene.  Lakeland Exterminator

6
[回复]
Clay Lowe 说:
2025年5月16日 01:35

It is very good, but look at the information at this address.  Search for a local number in the US or Canada here

7
[回复]
Clay Lowe 说:
2025年5月29日 04:10

I invite you to the page where     see how much we have in common. UPPERHOUSE

8
[回复]
Clay Lowe 说:
2025年7月16日 15:37

I can recommend primarily decent and even responsible tips, as a result view it: Smm panel cheap

9
[回复]
Clay Lowe 说:
2025年7月19日 07:35

On this page you can read       my interests, write something special. tribal court lawyer

10
[回复]
Clay Lowe 说:
2025年7月22日 15:37

I might suggest solely beneficial in addition to trusted facts, and so find it: ap33

11
[回复]
Clay Lowe 说:
2025年8月31日 16:25

This is very appealing, however , it is very important that will mouse click on the connection: 먹튀폴리스

12
[回复]
Anonymous 说:
2026年3月10日 11:23

There is so much in this article that I would never have thought of on my own. Your content gives readers things to think about in an interesting way. coupon codes


登录 *


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