最大字段和问题-（动态规划，分治法，简单算法）--C_给定由n个整数组成的序列a1,a2,…,an,序列中可能有负数,要在这n个数中选取相邻的

问题描述：给定由n个整数（可能有负整数）组成的序列（a1,a2,…,an），最大子段和问题要求该序列形如 的最大值（1<=i<=j<=n），当序列中所有整数均为负整数时，其最大子段和为0。

1.简单算法
代码如下：

#include<stdio.h>
#include<stdlib.h>

#define max 6

int MUL(int *p)
{
	int sum = 0, m = 0;

	for (int i = 0; i < max; i++)
	{
		if (p[i] > 0)//定位到序列中第一个正数
		{
			for (; i < max; i++)//从第一个正数开始
			{
				sum += p[i];//从第一个整数开始往后求和
				if (m < sum)
					m = sum;//m用来保存期间出现的最大和，即所求
			}
			break;//跳出循环，主要是跳出第一个for;他的作用只是定位到第一个，目的达到没必要进行
		}
	}
	return m;
}

int main()
{
	int a[max];//用来存储序列
	printf("请输入序列：");
	for (int i = 0; i < max; i++)
		scanf_s("%d", &a[i]);//vs中使用scanf_s,vc中scanf
	printf("最大字段和为：%d\n", MUL(a));
	system("PAUSE");
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

示例输入输出：

2.分治法
分治法的思想就是将完整的序列一分为二（下面称左段右段），分别求两段子序列的最大字段和来求解。最后结果会有三种情况
（1）整个序列的最大子字段（s）与左段最大子字段（s1）相同
（2）整个序列的最大子字段(s)与右段最大子字段（s2）相同
（3）整个序列的最大子字段(s)恰好横跨左右段，即左右段的最大子字段是整个序列最大子字段的子字段(s=s1+s2)
代码如下：

#include<stdio.h>
#include<stdlib.h>

#define max 6
int MaxSubSum(int *a, int left, int right)//参数为数组a，left表示数组左下标，right表示数组右下标
{
	int sum = 0;
	if (left == right)//序列长度为一的情况
		sum = a[left] > 0 ? a[left] : 0;
	else
	{
		int center = (left + right) / 2;//center为数组中间下标
		int leftsum = MaxSubSum(a, left, center);//求leftsum数组左段和
		int rightsum = MaxSubSum(a, center + 1, right);//求rightsum数组右段和

		int s1 = 0;//记录左段最大字段和
		int lefts = 0;
		for (int i = center; i >= left; i--)
		{
			lefts += a[i];
			if (lefts > s1)
				s1 = lefts;
		}

		int s2 = 0;//记录右段最大字段和
		int rights = 0;
		for (int i = center + 1; i <= right; i++)
		{
			rights += a[i];
			if (rights > s2)
				s2 = rights;
		}
		//分治法三种情况比较，确定整个序列最大字段和
		sum = s1 + s2;
		if (sum < leftsum)
			sum = leftsum;
		if (sum < rightsum)
			sum = rightsum;
	}
	return sum;
}
//辅助调用，可替掉
int MaxSum(int n, int *a)
{
	return MaxSubSum(a, 1,n);
}
int main()
{
	int a[max];
	printf("请输入序列：");
	for (int i = 1; i <= max; i++)
		scanf_s("%d", &a[i]);
	printf("最大字段和为：%d\n", MaxSum(max, a));
	system("PAUSE");
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

示例输入输出

3.动态规划
代码如下：

#include<stdio.h>
#include<stdlib.h>
#define MAX 6
//本例为最大m子段和问题解法，最大子段和为本例中m=1时的特殊情况
int MaxSum(int m, int n, int *a)
{
	if (n < m || m < 1)
		return 0;
	int *b = new int[n + 1];
	int *c = new int[n + 1];
	b[0] = 0;
	c[1] = 0;
	for (int i = 1; i <= m; i++)
	{
		b[i] = b[i - 1] + a[i];
		c[i - 1] = b[i];
		int max = b[i];
		for (int j = i + 1; j <= i + n - m; j++)
		{
			b[j] = b[j - 1] > c[j - 1] ? b[j - 1] + a[j] : c[j - 1] + a[j];
			c[j - 1] = max;
			if (max < b[j])
				max = b[j];
		}
		c[i + n - m] = max;
	}
	int sum = 0;
	for (int j = m; j <= n; j++)
		if (sum < b[j])
			sum = b[j];
	return sum;
}
int main()
{
	int a[MAX];
	printf("请输入序列：");
	for (int i = 1; i <= MAX; i++)
	{
		scanf_s("%d", &a[i]);
	}
	printf("最大子字段和为：%d\n", MaxSum(1, MAX, a));
	system("PAUSE");
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

参考算法与设计第五版王晓东
为表述清楚，增加了许多不必要代码，可自行优化
学习中，欢迎交流，指导