最大子列和的四种算法及其时间复杂度分析

简介: 最大子列和的四种算法及其时间复杂度分析暴力破解法O(n^3)、暴力破解法改进版O(n^2);分而治之法O(nlogn)、在线处理算法O(n)。

最大子列和的四种算法

题目描述:
给定n个整数序列{A1,A2,...,An},求函数 f(i,j)=max{ 0,sum(ai,a(i+1),...,aj)}的最大值。
算法一:暴力破解法

​ 算出所有的子列和,找出最大的,即为所求。

​ 代码如下:

int maxSubseqSum1(int a[]) {
    int preSum = -1, maxSum = -1;                    //presentSum记录当前Sum,MaxSum记录最大子列和。
    int left = -1, right = -1;                       //left、right记录最大子列的左右端点值。
    for (int i = 0; i < n; i++) {                    //i记录左端点
        for (int j = i; j < n; j++) {                //j记录右端点
            preSum = 0;
            for (int k = i; k <= j; k++) {
                preSum += a[k];                     //累加计算a[i]->a[j]的子列和
            }
            if (preSum > maxSum) {
                maxSum = preSum;                    //更新最大值及其对应的左右边界
                left = i;
                right = j;
            }
        }
    }
    printf("in maxSubseqSum1() left=%d,right=%d,maxSum=%d\t暴力破解法\n", left, right, maxSum);
    return maxSum;
}

​ 时间复杂度较容易由3层嵌套for循环得出为

​ 可改进的主要点在于,如已知当前从i到j的子列和时,再计算i到j+1的子列和时,i到j的子列和又重新算一遍,显然是冗余的,是完全没有必要的,只需加一个j+1元素即可。

​ 那么可以改进之后可以得出算法2。

image.png

算法二:暴力破解法改进版

​ 同样为,算出所有的子列和,找出最大的,即为所求。但在具体是线上进行改进。

​ 代码如下:

int maxSubseqSum2(int a[]) {
    int preSum = -1, maxSum = -1;          //presentSum记录当前Sum,MaxSum记录最大子列和。
    int left = -1, right = -1;             //left、right记录最大子列的左右端点值。
    for (int i = 0; i < n; i++) {          //i记录左端点
        preSum = 0;
        for (int j = i; j < n; j++) {      //j记录右端点
            preSum += a[j];                //对于相同的i不同的j,只需在j-1层循环的基础上加一项a[j]即可。
            if (preSum > maxSum) {
                maxSum = preSum;           //更新最大值及其对应的左右边界
                left = i;
                right = j;
            }
        }
    }
    printf("in maxSubseqSum2() left=%d,right=%d,maxSum=%d\t暴力破解改进版算法\n", left, right, maxSum);
    return maxSum;
}

​ 改进版在对于相同的i不同的j的子列和计算时,在j-1层循环的基础上加一项a[j]的即可得出i到j的子列和。

​ 不难看出该算法的时间复杂度为T(n)=O(n^2)。较法一已经有较大提升。

​ 但是,当n到达10000、100000 、1000000时仍为一个较恐怖的的时间复杂度,因此借用分而治之的思想提出更好的算法三。

算法三:分而治之(分治法)

分治法是基于多项分支递归的一种很重要的算法。“分而治之”就是把一个复杂的问题分成两个或更多的相同或相似的子问题,直到最后子问题可以简单的直接求解,原问题的解即为子问题的解的合并。诸如快速排序、归并排序、傅里叶变换、快速傅里叶变换等算法都极大程度上采用了分治法的基本思想。

​ 分治法通常以数学归纳法来验证。而其复杂度多数情况下是以解递推关系式来判定。

​ 运用到最大子列和问题中就可简述为:先“分”,即将数列分为两半,最大子列必只有左半边、右半边、或者两者中间这三种情况,依次求出三种情况的解;再“治”,求三个最大子列和的最大解即可得到整个数列的最大子列和。

​ 依据上述思想可得出该题的分治算法简要的四步:

  1. 将数列从中间分为两个等长或者数量差值为1的两个子数列。
  2. 递归使用该算法分别求出左半边的最大子列和和右半边的最大子列和。
  3. 计算跨越中线的最大子列和,即从中线开始向左右两边分别遍历,得出跨越中线的最大子列和。
  4. 求三者的最大值即可。

其代码具体描述如下:

//分治法递归求最大子列和
int divCon(int list[], int left, int right) {
    int maxLeftSum, maxRightSum;              //记录左右两边数列的最大子列和
    int maxLBorderSum = 0, maxRBorderSum = 0; //记录跨越中线的最大子列和

    if (left == right) {                      //当left=right时,表示当前递归到只有一个数字的子列
        if (list[left] > 0) {
            return list[left];                //若该值>0则表示可以使最大子列和增加,故返回改值。
        } else
            return 0;                         //若改值<=0则表示不能增大最大子列和返回0。
    }

    //“分”
    int center = (left + right) / 2;                   //计算中间点
    maxLeftSum = divCon(list, left, center);           //递归解决左半边最大子列和
    maxRightSum = divCon(list, center + 1, right);     //递归解决左半边最大子列和

    //求跨越边界的最大子列和。
    int leftBorderSum = 0, rightBorderSum = 0; //记录向左、向右的边界上当前扫描的和
    //求中线以左的最大值
    for (int i = center; i >= left; i--) {
        leftBorderSum += list[i];
        if (leftBorderSum > maxLBorderSum)     //如果当前扫描的左半边的和大于左半边整体的和则更新最大值
            maxLBorderSum = leftBorderSum;
    }
    //求中线以右的最大值
    for (int i = center + 1; i < right; i++) {
        rightBorderSum += list[i];
        if (rightBorderSum > maxRBorderSum)    //如果当前扫描的左半边的和大于左半边整体的和则更新最大值
            maxRBorderSum = rightBorderSum;
    }

    //“治”   求左数列、右数列、跨越边界的数列,三个子问题的最大解。
    return maxOfThNum(maxLeftSum, maxRightSum, maxLBorderSum + maxRBorderSum);
}

//求三个数的最大值函数
int maxOfThNum(int a, int b, int c) {
    return a > b ? a > c ? a : c : b > c ? b : c;
}

int maxSubseqSum3(int list[]) {
    int maxSum = divCon(list, 0, n - 1);
    printf("in maxSubseqSum3() maxSum=%d\t分而治之算法\n", maxSum);
    return maxSum;
}

​ 分治法主要分为三个部分进行求解,因此时间复杂度的计算也应该分为三部分,其中在“分”的过程中每一半都为$T(n/2)$,故左右两部分的时间复杂度为$2T(n/2)$;对于跨越中线的子列和是通过两个for循环分别求解中线以左、以右的两部分的子列和,因此最差时间复杂度为遍历整个数组,故而时间复杂度为$T(n)$。

​ 综上所述,对于时间复杂度可得如下递推式:
image.png

​ 通过对数列的数次分割,直至被分为1个数组元素时满足$n/2^k=1$,即为$2^k=n$,因此可以得到时间复杂度为:
image.png

​ 对比于暴力破解法,时间复杂已经有一个不错的提升,比如当n的数量级来到$10^4$时,已经有较为优异的表现。

​ 但是,在该算法的第6~11行及21~31行我们不难发现这样子一个规律:当某子列为正数时可以增大最大子列和,若为负数则不可能使得最大子列和增加。

​ 因此进一步分析可以得出方法四:在线处理算法。

算法四:在线处理算法

​ 通过“在线的”思想,即无须获取全部数组元素就可以进行先行处理,可以对输入的每一个数据进行立即处理,使得算法的结果是对于当前已经读入的数据都成立的解。也就是说当某个地方的输入发生中断时,程序可以返回当前已经输入的数据的正确当前解。因此在线思想是完全区别于上述所提的三种算法的。

​ 在线处理算法的核心思想为:

​ 如果整数序列{a1,a2,...,an}的最大子列和是{ai,a(i+1),...,aj},那么必有(ai+a(i+1)+...+al>=0)对任意的i<=l<=j成立。因此,当某当前子列为负时,则应考察新的以i+1为左边界的子列进行计算。

​ 其代码具体描述如下:

int maxSubseqSum4(int list[]) {
    int preSum = 0, maxSum = 0;     //preSum记录当前子列和,maxSum记录最大子列和
    int left = -1, right = -1;      //标记最大子列的左右边界
    for (int i = 0; i < n; i++) {
        preSum += list[i];          //累加下一个元素
        if (preSum > maxSum) {      //若累加后当前子列和大于最大子列和则更新
            maxSum = preSum;
            right = i;              //修改右边界指针
        } else if (preSum < 0) {    //若累加使得当前子列和变为负数,则应当丢弃该子列。
            preSum = 0;             //因为其不可能使最大子列和增大。
            left = i+1;             //修改左边界指针
        }
    }
    printf("in maxSubseqSum4() left=%d,right=%d,maxSum=%d\t在线处理算法\n", left, right, maxSum);
    return maxSum;
}

​ 对于该算法的时间复杂度由算法代码较易得出为T(n)=O(n),但是优秀的算法,因其思想与普通算法思想有较大的差异,所以导致算法的正确性表现的不是很直观,需要通过实际例子深入理解。

                                                          by...Ss1Two...2023/01/03
目录
相关文章
|
26天前
|
机器学习/深度学习 人工智能 监控
AI算法分析,智慧城管AI智能识别系统源码
AI视频分析技术应用于智慧城管系统,通过监控摄像头实时识别违法行为,如违规摆摊、垃圾、违章停车等,实现非现场执法和预警。算法平台检测街面秩序(出店、游商、机动车、占道)和市容环境(垃圾、晾晒、垃圾桶、路面不洁、漂浮物、乱堆物料),助力及时处理问题,提升城市管理效率。
AI算法分析,智慧城管AI智能识别系统源码
|
30天前
|
算法
经典控制算法——PID算法原理分析及优化
这篇文章介绍了PID控制算法,这是一种广泛应用的控制策略,具有简单、鲁棒性强的特点。PID通过比例、积分和微分三个部分调整控制量,以减少系统误差。文章提到了在大学智能汽车竞赛中的应用,并详细解释了PID的基本原理和数学表达式。接着,讨论了数字PID的实现,包括位置式、增量式和步进式,以及它们各自的优缺点。最后,文章介绍了PID的优化方法,如积分饱和处理和微分项优化,以及串级PID在电机控制中的应用。整个内容旨在帮助读者理解PID控制的原理和实际运用。
70 1
|
1月前
|
机器学习/深度学习 存储 缓存
数据结构从入门到精通——算法的时间复杂度和空间复杂度
算法的时间复杂度和空间复杂度是评估算法性能的两个重要指标。时间复杂度主要关注算法执行过程中所需的时间随输入规模的变化情况,而空间复杂度则关注算法执行过程中所需的最大存储空间或内存空间。
61 0
|
1月前
|
算法 调度
【算法设计与分析】— —基础概念题(one)可作为日常联系或期末复习
【算法设计与分析】— —基础概念题(one)可作为日常联系或期末复习
47 1
|
1月前
|
算法 C语言 C++
嵌入式PID算法理论+实践分析
嵌入式PID算法理论+实践分析
23 0
|
1月前
|
算法
关联规则分析(Apriori算法2
关联规则分析(Apriori算法2
34 0
|
1天前
|
算法 数据可视化 Python
Python中LARS和Lasso回归之最小角算法Lars分析波士顿住房数据实例
Python中LARS和Lasso回归之最小角算法Lars分析波士顿住房数据实例
|
2天前
|
算法 定位技术 Windows
R语言最大流最小割定理和最短路径算法分析交通网络流量拥堵问题
R语言最大流最小割定理和最短路径算法分析交通网络流量拥堵问题
10 4
|
25天前
|
算法
TOP-K问题和向上调整算法和向下调整算法的时间复杂度问题的分析
TOP-K问题和向上调整算法和向下调整算法的时间复杂度问题的分析
17 1
|
27天前
|
算法
PID算法原理分析及优化
这篇文章介绍了PID控制方法,一种广泛应用于机电、冶金等行业的经典控制算法。PID通过比例、积分、微分三个部分调整控制量,以适应系统偏差。文章讨论了比例调节对系统响应的直接影响,积分调节如何消除稳态误差,以及微分调节如何减少超调。还提到了数字PID的实现,包括位置式、增量式和步进式,并探讨了积分饱和和微分项的优化策略。最后,文章简述了串级PID在电机控制中的应用,并强调了PID控制的灵活性和实用性。
38 1