最大子数组的线性时间的算法

问题来源：

这是真的牛批，没有答案，

这是:MaxSubLinear.h头文件:定义了一个类，用于求给定数组的最大子数组，成员变量和成员函数的说明如下:

成员变量:

　　begin_index:最大子数组的起始索引;

　　end_index:最大子数组的终止索引;

成员函数:

　　maxSubArray:给定一个数组和其长度,返回最大子数组的和,参数返回起始索引和终止索引;

　　linearMaxSubArray:上面函数的改进版本,100%线性时间;

　　getBeginIndex和getEndIndex用于获取起始索引和终止索引;

#pragma once
class MaxSubLinear
{
public:
MaxSubLinear();
~MaxSubLinear();
static int maxSubArray(int* arr, int length, int& begin_index = begin_index, int& end_index = end_index);
static int linearMaxSubArray(int* arr, int length, int& begin_index = begin_index, int& end_index = end_index);
static int getBeginIndex() { return begin_index; }
static int getEndIndex() { return end_index; }
private:
static int begin_index;
static int end_index;
};

现在需要根据题目的提示,实现最大子数组的函数:

　　由题目,假设我们已知 A[1...j] 的最大子数组,设该最大子数组为:max_sub_array,接下来要求 A[1... j + 1]的最大子数组,那么A[1...j+1]的最大子数组不外乎两种情况:

　　　　1.A[1... j+1]的最大子数组还是原来A[1...j]的最大子数组max_sub_array;

　　　　2.A[1...j+1]的最大子数组是A[i ... j+1],其中1 <= i <=j+1;

　　算法的核心就是如何从A[1..j]的最大子数组求出A[1..j+1]的最大子数组;

按照上面的分析,自然而然的可以想到如下的算法:

　　INT_MIN 是 limits.h 中定义的一个常量,表示最小的int值,

int MaxSubLinear::maxSubArray(int* arr, int length, int& begin_index, int& end_index)
{
int max_sub_sum = INT_MIN;
int temp_sum = 0;
for (int i = 0; i for (int j = i; j >= 0; j--) {
temp_sum += arr[j];
if (temp_sum > max_sub_sum) {
max_sub_sum = temp_sum;
begin_index = j;
end_index = i;
}
}
temp_sum = 0;
}
return max_sub_sum;
}

　　该算法基于如下思想:要从A[1...j]扩展到A[1...j+1],

　　　　1.先求出A[1...j+1]包含j+1的子数组的最大值,记为temp_sum;

　　　　2.将temp_sum和A[1...j]的最大子数组max_sub_sum进行比较,取其中的较大者为A[1...j+1]的最大子数组

　　这个算法很好理解,上面内层的for循环就是求A[1...j+1]的包含j+1索引的最大子数组的过程;

　　但遗憾的是这个算法并不是线性时间复杂度的,算法时间复杂度分析如下

　　　　i = 0,内层循环1次

　　　　i=1,内层循环2次

　　　　...

　　　　i=length - 1,内层循环length次

　　很明显,这是一个等差数列求和公式

　　所以还是一个 复杂度的算法.

　　当然该算法还可以优化:当arr[i] 为负数时,可以直接判断A[1...j+1]的最大子数组还是原来的A[1...j]的最大子数组,优化后的代码如下:

int MaxSubLinear::maxSubArray(int* arr, int length, int& begin_index, int& end_index)
{
int max_sub_sum = INT_MIN;
int temp_sum = 0;
for (int i = 0; i if (arr[i] <0) {
continue;
}
for (int j = i; j >= 0; j--) {
temp_sum += arr[j];
if (temp_sum > max_sub_sum) {
max_sub_sum = temp_sum;
begin_index = j;
end_index = i;
}
}
temp_sum = 0;
}
return max_sub_sum;
}

可以看到在内层循环开始前,先判断当前元素的正负,如果为负,可以断定,新的最大子数组还是原来的,直接开始下轮循环.但是,这种优化依然不能改变双重循环的事实,算法依然是 的.

正如牛顿说的,为什么他看的比别人远,因为他站在巨人的肩膀上,为达到真理所做的任何努力都不会白费的,当实现上述算法的时候,我们离线性时间复杂度仅一步之遥了.

分析下上述算法的内层循环,内层循环的功能是求A[1...j+1]的包含j+1索引的最大子数组,只要能够不使用循环求出A[1...j+1]的包含j+1索引的最大子数组就能实现线性时间复杂度,

　　就像保存A[1...j]的最大子数组一样,我们可以添加一个变量用于保存A[1...j]的包含j索引的最大子数组;

　　这样我们就能通过常数步骤实现包含最右边界的最大子数组的扩展.基于这种思想,线性时间复杂度算法如下:

1 int MaxSubLinear::linearMaxSubArray(int* arr, int length, int& begin_index, int& end_index)
2 {
3 int max_sub_sum = INT_MIN;
4 begin_index = end_index = -1;
5
6 int max_sub_include_right = INT_MIN;//包含最有边元素的最大子数组
7 int maybe_begin_index = -1;
8 int maybe_end_index = -1;
9
10 for (int i = 0; i 11 //先求出新的包含最右元素的新的最大子数组
12 if (max_sub_include_right+arr[i] > arr[i]) {
13 max_sub_include_right += arr[i];
14 maybe_end_index = i;
15 }
16 else {
17 max_sub_include_right = arr[i];
18 maybe_begin_index = i;
19 }
20 //取 包含最右元素的子数组 和 以前的最大子数组 中的最大者
21 if (max_sub_sum 22 max_sub_sum = max_sub_include_right;
23 end_index = maybe_end_index;
24 begin_index = maybe_begin_index;
25 }
26 }
27 return max_sub_sum;
28 }

变量max_sub_include_right保存了包含目前最右索引的最大子数组的和,
maybe_begin_index和maybe_end_index分别是其左边界和右边界索引;

当需要向右扩展max_sub_include_right的时候,通过和新的最右边界arr[i] 相加再和max_sub_include_right比较来重新给表示包含有边界的三个变量max_sub_include_right,maybe_begin_index和maybe_end_index赋值;

最后再将包含右边界的最大子数组和原来的最大子数组比较来获得新的最大子数组.

MaxSubLinear.cpp的完整实现如下:

1 #include "MaxSubLinear.h"
2 #include "limits.h"
3
4
5 MaxSubLinear::MaxSubLinear()
6 {
7 }
8
9
10 MaxSubLinear::~MaxSubLinear()
11 {
12 }
13
14 //静态成员变量在类外面必须初始化
15 int MaxSubLinear::begin_index = 0;
16 int MaxSubLinear::end_index = 0;
17
18 int MaxSubLinear::maxSubArray(int* arr, int length, int& begin_index, int& end_index)
19 {
20 int max_sub_sum = INT_MIN;
21 int temp_sum = 0;
22 for (int i = 0; i 23 if (arr[i] <0) {
24 continue;
25 }
26 for (int j = i; j >= 0; j--) {
27 temp_sum += arr[j];
28 if (temp_sum > max_sub_sum) {
29 max_sub_sum = temp_sum;
30 begin_index = j;
31 end_index = i;
32 }
33 }
34 temp_sum = 0;
35 }
36 return max_sub_sum;
37 }
38
39 int MaxSubLinear::linearMaxSubArray(int* arr, int length, int& begin_index, int& end_index)
40 {
41 int max_sub_sum = INT_MIN;
42 begin_index = end_index = -1;
43
44 int max_sub_include_right = INT_MIN;//包含最有边元素的最大子数组
45 int maybe_begin_index = -1;
46 int maybe_end_index = -1;
47
48 for (int i = 0; i 49 //先求出新的包含最右元素的新的最大子数组
50 if (max_sub_include_right+arr[i] > arr[i]) {
51 max_sub_include_right += arr[i];
52 maybe_end_index = i;
53 }
54 else {
55 max_sub_include_right = arr[i];
56 maybe_begin_index = i;
57 }
58 //取 包含最右元素的子数组 和 以前的最大子数组 中的最大者
59 if (max_sub_sum 60 max_sub_sum = max_sub_include_right;
61 end_index = maybe_end_index;
62 begin_index = maybe_begin_index;
63 }
64 }
65 return max_sub_sum;
66 }

对算法的测试代码如下:

int main()
{
// 18,20,-7,12
// 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
int a[] = { 13,-3,-25,20,-3,-16,-23,18,20,-7,12,-5,-22,15,-4,7 };
int length = sizeof(a) / sizeof(a[0]);
int begin_index = 0, end_index = 0, max_sum = 0;
max_sum = MaxSubLinear::linearMaxSubArray(a, length);
cout <<"最大子数组从:" <}

运行结果如下: