总和最大区间问题

前言

最近在看从这位大佬借的 《计算之魂》这本书，感觉光看书也就图一乐，看完仍旧是脑袋空空，还是得敲敲代码才能记得牢。

问题描述

给定一个实数序列，设计一个最有效的算法，找到一个总和最大的区间。

三重循环方法

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
result TripleLoop(double*p, int length)
{
	double max = 0;
	int start = 0, end = 0;
	for (int i = 0; i < length; i++)
	{
		for (int j = i; j < length; j++)
		{
			double temp = 0;
			for (int k = i; k < j; k++)
			{
				temp = temp + *(p + k);
			}
			if (temp > max)
			{
				max = temp;
				start = i;
				end = j-1;
			}
		}
	}
	result MyResult;
	MyResult.value = max;
	MyResult.start_num = start;
	MyResult.end_num = end;
	return MyResult;
}

两重循环方法

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
result DoubleLoop(double* p, int length)
{
	double max = 0;
	int start = 0, end = 0;
	for (int i = 0; i < length; i++)
	{
		double sum = *(p + i);
		if (max < sum)
		{
			max = sum;
			start = i;
			end = i;
		}
		for (int j = i + 1; j < length; j++)
		{
			sum = sum + *(p + j);
			if (max < sum)
			{
				max = sum;
				start = i;
				end = j;
			}
		}
	}
	result MyResult;
	MyResult.value = max;
	MyResult.start_num = start;
	MyResult.end_num = end;
	return MyResult;
}

分治法

在看分治法查找资料时，发现书上写的分治法是错的。《计算之魂》第 37 页关于分治法的部分解释原文如下。

前后两个子序列的总和最大区间中间有间隔，我们假定这两个子序列的总和最大区间分别是 $[p_1,q_1]$ 和 $[p_2,q_2]$。这时，整个序列的总和最大区间是下面三者中最大的那一个：
（1）$[p_1,q_1]$
（2）$[p_2,q_2]$
（3）$[p_1,q_2]$

在参考链接的评论区里有位同志给出的例子如下：

序号 0 1 2 3 4 5
数值 8 -10 7 8 -9 9

按照书中解释，首先将其分为两个子序列，即 $[p_1,q_1] = [0,0]$, $[p_2,q_2] = [5,5]$。这时，整个序列的总和最大区间是下面三者中最大的那一个：

  1. $[p_1,q_1] = [0,0] = 8$
  2. $[p_2,q_2] = [5,5] = 9$
  3. $[p_1,q_2] = [0,5] = 13$

但是实际上最大的区间应该是$[2,3] = 15$.

对比

对三重循环方法和两重循环方法进行对比，对于相同的长度为 2000 的随机数组，处理的时间对比如下所示：

完整代码

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
#include <iostream>
#include<stdlib.h> 
#include<time.h> 

// 给定一个实数序列，求总和最大区间

#define LENGTH 2000

typedef struct result {
	int start_num;
	int end_num;
	double value;
};

clock_t time_start, time_finish;

// [a,b]范围内随机数,最多bit位小数
void init(double*p, int a, int b, int bit)
{
	srand(time(nullptr));
	for (int i = 0; i < LENGTH; i++)
	{
		int temp_front, temp_back;
		temp_front = a + rand() % (b - a + 1);  // 小数点前
		temp_back = rand() % (int)pow(10, bit);
		*(p+i) = (double)(temp_front) +((double)temp_back * (double)pow(10, -bit));
	}
}

result TripleLoop(double*p, int length)
{
	double max = 0;
	int start = 0, end = 0;
	for (int i = 0; i < length; i++)
	{
		for (int j = i; j < length; j++)
		{
			double temp = 0;
			for (int k = i; k < j; k++)
			{
				temp = temp + *(p + k);
			}
			if (temp > max)
			{
				max = temp;
				start = i;
				end = j-1;
			}
		}
	}
	result MyResult;
	MyResult.value = max;
	MyResult.start_num = start;
	MyResult.end_num = end;
	return MyResult;
}

result DoubleLoop(double* p, int length)
{
	double max = 0;
	int start = 0, end = 0;
	for (int i = 0; i < length; i++)
	{
		double sum = *(p + i);
		if (max < sum)
		{
			max = sum;
			start = i;
			end = i;
		}
		for (int j = i + 1; j < length; j++)
		{
			sum = sum + *(p + j);
			if (max < sum)
			{
				max = sum;
				start = i;
				end = j;
			}
		}
	}
	result MyResult;
	MyResult.value = max;
	MyResult.start_num = start;
	MyResult.end_num = end;
	return MyResult;
}

int main()
{
	double value[LENGTH];
	init(value, -100, 100, 2);
	result DoubleResult, TripleResult;
	time_start = clock();
	DoubleResult = DoubleLoop(value, LENGTH);
	time_finish = clock();
	std::cout << "the DoubleLoop cost is:" << time_finish - time_start << std::endl;
	std::cout << "DoubleLoop value = " << DoubleResult.value << std::endl;
	std::cout << "DoubleLoop start_num = " << DoubleResult.start_num << std::endl;
	std::cout << "DoubleLoop end_num = " << DoubleResult.end_num << std::endl;
	std::cout << std::endl;;
	time_start = clock();
	TripleResult = TripleLoop(value, LENGTH);
	time_finish = clock();
	std::cout << "the TripleLoop cost is:" << time_finish - time_start << std::endl;
	std::cout << "TripleLoop value = " << TripleResult.value << std::endl;
	std::cout << "TripleLoop start_num = " << TripleResult.start_num << std::endl;
	std::cout << "TripleLoop end_num = " << TripleResult.end_num << std::endl;
	
	return 0;
}


参考链接

CSDN