最大子段和问题 蛮力法、分治法和动态规划效率比较（C++实现）_最大字段和蛮力法c++并测试时间

进行比较的代码如下，其中分别给出了用蛮力法、分治法和动态规划法求解最大子段和问题的函数：

#include<iostream>
#include<ctime>
using namespace std;

const int length = 1000;

//用于求三个数中最大值的辅助函数，由于内容少，定义为内联函数以提高效率
inline int max(const int& x1, const int& x2, const int& x3)
{
	if (x1 >= x2 && x1 >= x3)
	{
		return x1;
	}
	else if (x2 >= x1 && x2 >= x3)
	{
		return x2;
	}
	else return x3;
}

//蛮力法求解，即求出数组的所有子段并分别计算子段和，从子段和中选择最大值
int BruteForce(const int* a, const int& n)
{
	int max = 0;
	for (int length = 1; length <= n; length++)//对于每一种可能长度都需要求出子段和
	{
		for (int i = 0; i <= n - length; i++)//对于子段长度相同的不同子段也需要分别求出子段和
		{
			int sum = 0;
			for (int j = i; j < i + length; j++)
			{
				sum += a[j];
			}
			if (sum > max)//每求出一个子段和就与当前最大子段和进行比较，如果新求出的子段和更大则更新当前最大子段和
			{
				max = sum;
			}
		}
	}
	return max;//返回求出的所有子段和中的最大值
}

//分治法求解，对于任意一个数组，其子段和无非可以分为三种情况：最大和对应子段在数组的左半段、最大和对应的子段在数组的右半段、最大和对应的子段跨越了数组的中点
int DivideConquer(const int* a, const int& left, const int& right)//区间的形式采用左闭右开
{
	//首先处理递归基，也就是数组中只包含一个元素的情况，这时根据最大子段和的定义，如果该元素是正数则结果为其自身，否则结果为0
	if (right - left <= 1)
	{
		if (a[left] > 0)
		{
			return a[left];
		}
		else return 0;
	}
	int middle = (left + right) >> 1;//首先找到数组的中点，方便后续处理
	int leftMax = 0, rightMax = 0;
	int leftSum = 0, rightSum = 0;
	//分别以数组的中点为基准，分别找出其向左和向右方向的最大子段长度
	for (int i = middle - 1; i >= left; i--)
	{
		leftSum += a[i];
		if (leftSum >= leftMax)
			leftMax = leftSum;
	}
	for (int i = middle; i < right; i++)
	{
		rightSum += a[i];
		if (rightSum >= rightMax)
			rightMax = rightSum;
	}
	//从三种情况中选择最大的一种，三种情况分别是最大和子段在数组左半段，最大和子段在数组右半段，最大和数组跨越了数组中点（此处使用了辅助函数max用于求出三个数中的最大值）
	return max(DivideConquer(a, left, middle), DivideConquer(a, middle, right), leftMax + rightMax);
}

//动态规划法求解，使用一个数组temp，temp[i]可以理解为到第i号元素为止最大子段和的长度
int DynamicProgram(int* a,const int& n)
{
	int* temp = new int[n];
	temp[0] = a[0] > 0 ? a[0] : 0;
	for (int i = 1; i < n; i++)
	{
		temp[i] = temp[i - 1] > 0 ? (temp[i - 1] + a[i]) : a[i];
	}
	int max = 0;
	for (int i = 0; i < n; i++)
	{
		if (temp[i] > max)
			max = temp[i];
	}
	return max;
}



int main(void)
{
	//首先创建一个指定长度的整数数组
	int* array = new int[length];
	int result;
	clock_t start, end;
	double TimeGap;
	srand(1);//固定随机数种子，方便后续多次调试
	for (int i = 0; i < length; i++)
	{
		array[i] = rand() % 21 - 10;//采用随机数的方法给数组元素赋值（正数与负数出现的概率均等）
	}

	//首先采用蛮力法求解该问题并计算运行时间
	start = clock();
	result = BruteForce(array, length);
	end = clock();
	TimeGap = double((end - start) / CLK_TCK);
	cout << "蛮力算法的运行结果为：" << result << "，求解时间为：" << TimeGap << "ms" << endl;

	//接着采用分治法求解该问题并计算运行时间
	start = clock();
	result = DivideConquer(array, 0, length);
	end = clock();
	TimeGap = double((end - start) / CLK_TCK);
	cout << "分治算法的运行结果为：" << result << "，求解时间为：" << TimeGap << "ms" << endl;

	//最后采用动态规划求解该问题并计算运行时间
	start = clock();
	result = DynamicProgram(array, length);
	end = clock();
	TimeGap = double((end - start) / CLK_TCK);
	cout << "动态规划算法的运行结果为：" << result << "，求解时间为：" << TimeGap << "ms" << endl;

	delete[]array;
	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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131

用户可以根据修改符号常量length来测试不同长度数组进行最大子段和查找时的时间。
1.数组长度为1000时：

此时由输出结果可知三种算法的时间复杂度还没有发生显著差异；
2.数组长度为5000时：

由图可知此时蛮力法的运行时间已经远远高于分治法和动态规划算法，因此接下来只对数据规模更大时的分治算法和动态规划算法进行比较；
3.数组长度为20000000（两千万）时：

此时终于出现分水岭，分治算法的运行时间开始逐渐高于动态规划算法。

综上所属，时间性能比较：动态规划算法>分治算法>蛮力算法
原因分析：动态规划算法的时间复杂度为O(n)，分治算法的时间复杂度为O(nlogn)，而蛮力算法的时间复杂度为O(2n)，因此随着问题规模的增加，最终的运行时间总会呈现：动态规划时间最短，分治算法的时间次之，蛮力算法的时间最长。