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

简介: 最大子列和的四种算法及其时间复杂度分析暴力破解法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
目录
相关文章
|
12月前
|
机器学习/深度学习 算法 搜索推荐
从理论到实践,Python算法复杂度分析一站式教程,助你轻松驾驭大数据挑战!
【10月更文挑战第4天】在大数据时代,算法效率至关重要。本文从理论入手,介绍时间复杂度和空间复杂度两个核心概念,并通过冒泡排序和快速排序的Python实现详细分析其复杂度。冒泡排序的时间复杂度为O(n^2),空间复杂度为O(1);快速排序平均时间复杂度为O(n log n),空间复杂度为O(log n)。文章还介绍了算法选择、分而治之及空间换时间等优化策略,帮助你在大数据挑战中游刃有余。
323 3
|
8天前
|
运维 监控 JavaScript
基于 Node.js 图结构的局域网设备拓扑分析算法在局域网内监控软件中的应用研究
本文探讨图结构在局域网监控系统中的应用,通过Node.js实现设备拓扑建模、路径分析与故障定位,提升网络可视化、可追溯性与运维效率,结合模拟实验验证其高效性与准确性。
65 3
|
4月前
|
机器学习/深度学习 边缘计算 算法
NOMA和OFDMA优化算法分析
NOMA和OFDMA优化算法分析
244 127
|
6月前
|
数据采集 机器学习/深度学习 算法
别急着上算法,咱先把数据整明白:大数据分析的5个基本步骤,你都搞对了吗?
别急着上算法,咱先把数据整明白:大数据分析的5个基本步骤,你都搞对了吗?
254 4
|
3月前
|
人工智能 自然语言处理 算法
2025 年 7 月境内深度合成服务算法备案情况分析报告
2025年7月,中央网信办发布第十二批深度合成算法备案信息,全国389款产品通过备案,服务提供者占比超七成。截至7月14日,全国累计备案达3834款,覆盖文本、图像、音视频等多模态场景,广泛应用于生活服务、医疗、金融等领域。广东以135款居首,数字人、AI客服等C端应用主导,民营企业成主力,国企聚焦公共服务。随着AI政策推动,备案已成为AI产品合规上线关键环节。
|
6月前
|
存储 监控 算法
员工行为监控软件中的 Go 语言哈希表算法:理论、实现与分析
当代企业管理体系中,员工行为监控软件已逐步成为维护企业信息安全、提升工作效能的关键工具。这类软件能够实时记录员工操作行为,为企业管理者提供数据驱动的决策依据。其核心支撑技术在于数据结构与算法的精妙运用。本文聚焦于 Go 语言中的哈希表算法,深入探究其在员工行为监控软件中的应用逻辑与实现机制。
148 14
|
12月前
|
机器学习/深度学习 缓存 算法
Python算法设计中的时间复杂度与空间复杂度,你真的理解对了吗?
【10月更文挑战第4天】在Python编程中,算法的设计与优化至关重要,尤其在数据处理、科学计算及机器学习领域。本文探讨了评估算法性能的核心指标——时间复杂度和空间复杂度。通过详细解释两者的概念,并提供快速排序和字符串反转的示例代码,帮助读者深入理解这些概念。同时,文章还讨论了如何在实际应用中平衡时间和空间复杂度,以实现最优性能。
204 6
|
7月前
|
自然语言处理 算法 安全
境内深度合成服务算法备案通过名单分析报告
本报告基于《境内深度合成服务算法备案通过名单》,分析了2023年6月至2025年3月公布的10批备案数据,涵盖属地分布、行业应用及产品形式等多个维度。报告显示,深度合成算法主要集中于经济发达地区,如北京、广东、上海等地,涉及教育、医疗、金融、娱乐等多行业。未来趋势显示技术将向多模态融合、行业定制化和安全合规方向发展。建议企业加强技术研发、拓展应用场景、关注政策动态,以在深度合成领域抢占先机。此分析旨在为企业提供参考,助力把握技术发展机遇。
境内深度合成服务算法备案通过名单分析报告
|
7月前
|
供应链 算法 搜索推荐
从公布的前十一批其他算法备案通过名单分析
2025年3月12日,国家网信办发布算法备案信息,深度合成算法通过395款,其他算法45款。前10次备案中,深度合成算法累计3234款,其他类别647款。个性化推送类占比49%,涵盖电商、资讯、视频推荐;检索过滤类占31.53%,用于搜索优化和内容安全;调度决策类占9.12%,集中在物流配送等;排序精选类占8.81%,生成合成类占1.55%。应用领域包括电商、社交媒体、物流、金融、医疗等,互联网科技企业主导,技术向垂直行业渗透,内容安全和多模态技术成新增长点。未来大模型检索和多模态生成或成重点。
从公布的前十一批其他算法备案通过名单分析
|
7月前
|
人工智能 自然语言处理 供应链
从第十批算法备案通过名单中分析算法的属地占比、行业及应用情况
2025年3月12日,国家网信办公布第十批深度合成算法通过名单,共395款。主要分布在广东、北京、上海、浙江等地,占比超80%,涵盖智能对话、图像生成、文本生成等多行业。典型应用包括医疗、教育、金融等领域,如觅健医疗内容生成算法、匠邦AI智能生成合成算法等。服务角色以面向用户为主,技术趋势为多模态融合与垂直领域专业化。

热门文章

最新文章