五种求解最大连续子数组的算法

求解最大连续子数组的内容在《算法导论》这本书上面是作为分治算法的一个例子来进行讲解的，书本上面内容（包括习题）提到了三种解决这一问题的算法，下面是我自己使用C++实现这三种方法的代码和思路放：

一、暴力解法

对数组内每一个数A[i]进行遍历，然后遍历以它们为起点的子数组，比较各个子数组的大小，找到最大连续子数组

#include "stdafx.h"
//暴力法求最大子数组和问题
int _tmain(int argc, _TCHAR* argv[])
{
    int A[8] = { -6, 10, -5, -3, -7, -1, -1 };
    int array_length = sizeof(A) / sizeof(A[0]);//数组大小
    int sum = -10000;//记录子数组的和
    int low;//记录子数组的底
    int height;//记录子数组的高
    for (int i = 0; i < array_length; i++)
    {
        for (int j = i ; j < array_length; j++)
        {
            int subarraysum=0;//所遍历出来的子数组的和
            //计算遍历的子数组之和
            for (int k = i; k <= j; k++)
            {
                subarraysum += A[k];
            }
            //找出最大的子数组
            if (subarraysum>sum)
            {
                sum = subarraysum;
                low = i;
                height = j;
            }
        }
    }
    printf("%d  %d  %d", low, height,sum);//将结果打印出来
    getchar();
    return 0;
}

可以看到这段程序里面一共嵌套着三层循环，除了最外面的循环会循环n次外内部的循环都比n次小，此程序的时间复杂度为O（n³）

二、分治法

这一算法在《算法导论》当中有很详细的说明，而且上面还有伪代码，我就不啰嗦了，直接放出我的实现代码。

 1 #include "stdafx.h"
 2 //分治法求最大子数组和问题
 3 struct PositioASum {
 4     int low;
 5     int high;
 6     int sum;
 7 };
 8 //寻找包含中点位置的最大子数组函数
 9 PositioASum MaxCrossingSubarray(int a[], int low, int mid, int high)
10 {
11     //求中点左边的最大值和最大位置
12     int maxLeft;//记录左边的最大位置
13     int maxSumLeft=-10000;//记录左边的最大和
14     int sumLeft=0;
15     for (int i = mid; i >= low; i--)
16     {
17         sumLeft += a[i];
18         if (sumLeft > maxSumLeft)
19         {
20             maxSumLeft = sumLeft;
21             maxLeft = i;
22         }
23     }
24     //求中点右边的最大值和最大位置
25     int maxRight=mid+1;//记录右边的最大位置
26     int maxSumRight = -10000;//记录右边的最大和
27     int sumRight = 0;//记录右边子数列的和
28     for (int i = mid+1; i <= high; i++)
29     {
30         sumRight += a[i];
31         if (sumRight > maxSumRight)
32         {
33             maxSumRight = sumRight;
34             maxRight = i;
35         }
36     }
37     PositioASum ps;
38     ps.low = maxLeft;
39     ps.high = maxRight;
40     ps.sum = maxSumLeft + maxSumRight;
41     return ps;
42 }
43 //分治法
44 PositioASum FindMaxSubArray(int a[], int low, int high)
45 {
46     if (low == high)
47     {
48         PositioASum ps;
49         ps.low = low;
50         ps.high = high;
51         ps.sum = a[low];
52         return ps;
53     }
54     else{
55         int mid = (low + high) / 2;
56         PositioASum left = FindMaxSubArray(a, low, mid);
57         PositioASum right = FindMaxSubArray(a, mid + 1, high);
58         PositioASum cross = MaxCrossingSubarray(a, low, mid, high);
59         if (left.sum >= cross.sum && left.sum >= right.sum)
60         {
61             return left;
62         }
63         else if (right.sum >= left.sum && right.sum >= cross.sum)
64         {
65             return right;
66         }else{
67             return cross;
68         }
69     }
70 }
71 
72 int _tmain(int argc, _TCHAR* argv[])
73 {
74     int A[8] = {-1,0,0,0,-1};
75     PositioASum result = FindMaxSubArray(A, 0, 4);
76     printf("%d  %d  %d", result.low, result.high, result.sum);//将结果打印出来
77     getchar();
78     return 0;
79 }

算法的时间复杂度为O（nlogn）,由于本程序是在数组的原地址上面进行的，所以总体的控件复杂度为递归的时间复杂度+数组所占的空间为S（n）+S（logn）=S(n)

三、根据书本后面习题所提供的方法

书本上面提出这样的一种方法：从数组的左边界开始，从左到右处理，记录到目前为止已经处理过的最大子数组。若已知A[1,2,....,j]的最大子数组，则A[1,2,.....,j,j+1]的最大子数组要么是A[1,2,....,j]的最大子数组，要么是某个子数组A[i,....,j+1](1<=i<=j+1)。基于这一思路我的实现过程如下：

 1 #include "stdafx.h"
 2 //基于算法导论上面的习题4.1-5来实现的算法
 3 int _tmain(int argc, _TCHAR* argv[])
 4 {
 5     int A[8] = { -6, 10, -5, 3, 7, -1, -1 };
 6     int array_length = sizeof(A) / sizeof(A[0]);//数组大小
 7     int maxSum = A[0];//记录最大子数组的和
 8     int low=0;//记录最大子数组的底
 9     int high=0;//记录最大子数组的高
10     for (int i = 0; i < array_length-1; i++)
11     {
12         int sum = 0;
13         //寻找以A[i+1]为终点的最大子数组
14         for (int j = i+1; j>=0; j--)
15         {
16             sum += A[j];
17             if (sum>maxSum)
18             {
19                 maxSum = sum;
20                 low = j;
21                 high = i + 1;
22             }
23         }
24     }
25     printf("%d  %d  %d", low, high,maxSum);//将结果打印出来
26     getchar();
27     return 0;
28 }

四、在线算法

//在线法求最大子数组和问题
int _tmain(int argc, _TCHAR* argv[])
{
    int A[8] = { -6, 10, -5, 6, -7, -1, -1 };
    int array_length = sizeof(A) / sizeof(A[0]);//数组大小
    int sum = 0;//记录子数组的和
    int thisSum = 0;
    int low=0;//记录子数组的底
    int height=0;//记录子数组的高
    for (int i = 0; i < array_length; i++)
    {
        thisSum += A[i];
        if (thisSum > sum)
        {
            sum = thisSum;
        }
        else if (thisSum < 0)
        {
            thisSum = 0;
        }
    }
    printf("%d",sum);//将结果打印出来
    getchar();
    return 0;
}

理解这个算法的关键是：使用thisSum来计算当前连续子数组的和，如果thisSum小于0，那么无论后面再加上什么数字都只会让子数组变小，所以抛弃当前子数组，重新开始计算子数组的值。

可以看到这个算法的时间复杂度为O（n）而且控件复杂度为S（n），是解决这一个问题非常有效的一个算法。

五、另外一种稍好的算法

 1 int _tmain(int argc, _TCHAR* argv[])
 2 {
 3     int n;//存储所输入的数组长度
 4     scanf("%d", &n);
 5     int* b = (int*)malloc(n*sizeof(int));//存储所出入的数组
 6     for (int i = 0; i < n; i++)
 7     {
 8         scanf("%d", &b[i]);
 9     }
10     int sum=0;//最大子数列和
11     //寻找最大子数列
12     for (int i = 0; i < n; i++)
13     {
14         int thisSum = 0;//当前数列
15         for (int j = i; j < n; j++)
16         {
17             thisSum += b[j];
18             if (thisSum>sum)
19             {
20                 sum = thisSum;
21             }
22         }
23     }
24     if (sum < 0)
25     {
26         printf("%d",0);
27     }else{
28         printf("%d", sum);
29     }
30     system("pause");
31     return 0;
32 }

相比于暴力解法每一次都从i到j地重新计算一次，这种算法每一次只需要在原来计算的基础上面加上一个数，所以这种算法少了一层循环,时间复杂度为O（n²）是一种比暴力解法要高效的解法

五种求解最大连续子数组的算法

相关推荐