选择特殊符号

选择搜索类型

热门搜索

首页 > 百科 > 建设工程百科

最大子数列问题

在计算机科学中,最大子数列问题的目标是在数列的一维方向找到一个连续的子数列,使该子数列的和最大。例如,对一个数列 −2, 1, −3, 4, −1, 2, 1, −5, 4,其连续子数列中和最大的是 4, −1, 2, 1, 其和为6。
该问题最初由布朗大学的Ulf Grenander教授于1977年提出,当初他为了展示数字图像中一个简单的最大似然估计模型。不久之后卡内基梅隆大学的Jay Kadane提出了该问题的线性算法。

最大子数列问题基本信息

最大子数列问题在线处理算法

最大子数列问题问题描述

最大连续子数列和一道很经典的算法问题,给定一个数列,其中可能有正数也可能有负数,我们的任务是找出其中连续的一个子数列(不允许空序列),使它们的和尽可能大。我们一起用多种方式,逐步优化解决这个问题。

最大子数列问题暴力方法

求出所有可能连续子列的和,时间复杂度O(N^3)

intMaxSubSequm1(intA[],intN){intThisSum,MaxSum=0;inti,j,k;for(i=0;i
 
  MaxSum)
MaxSum=ThisSum;
}}
returnMaxSum;
}

 

最大子数列问题一个简单的优化

很显然上面的算法中,在计算子列和时,可以利用前一步计算和的结果,不需要每次从头累加。时间复杂度O(N^2) 。

intMaxSubSequm1(intA[],intN){
intThisSum,MaxSum=0;
inti,j,k;
for(i=0;i
 
  MaxSum)
MaxSum=ThisSum;
}
}
returnMaxSum;
}

 

最大子数列问题分而治之

  1. 将问题一分为二,缩小问题规模,递归求解。

  2. 此处求解过程中要从中间基准点开始,扫描求出跨界的最大连续子列和,然后和左右边的解比较求出最终的结果。

  3. 时间复杂度O(N*logN)

最大子数列问题在线处理

我们可以通过抛弃负子列,保证最大子列和递增。当扫描一遍,最大子列和不再递增时,当前的最大子列和即为我们的解。这是最优算法,时间复杂度O(N)。

intMaxSubseqSum4(intA[],intN){
intThisSum,MaxSum;
inti;
ThisSum=MaxSum=0;
for(i=0;i
 
  MaxSum)
MaxSum=ThisSum;
elseif(ThisSum<0)
ThisSum=0;
}
returnMaxSum;
}

 

查看详情

最大子数列问题造价信息

  • 市场价
  • 信息价
  • 询价

大子弹头

  • 150间距 150高表面处理:静电喷涂;说明:6米以内长度定做;厚度:1.O厚;类型:铝合金吊顶;
  • m
  • 欧斯宝
  • 13%
  • 中山富申建筑装饰材料有限公司
  • 2022-12-07
查看价格

大子弹头挂片

  • 150 间距 150 高 1.8 厚 6 米以内长度定做
  • m
  • 欧斯宝
  • 13%
  • 厦门埃菲尔贸易有限公司
  • 2022-12-07
查看价格

大子弹头天线罩

  • 材质:玻璃钢;规格(mm):Ф316×636;壁厚(mm):5
  • 13%
  • 武汉工大创新玻璃钢科技发展有限公司
  • 2022-12-07
查看价格

理论最大相对密度仪

  • 品种:理论最大相对密度仪;
  • 京润浩
  • 13%
  • 宁夏华建建科商贸有限公司
  • 2022-12-07
查看价格

购买壁纸漆的时候需要注意的问题

  • 。/。 。
  • 华塑
  • 13%
  • 深圳市华塑装饰材料有限公司
  • 2022-12-07
查看价格

造价通是不是出问题了很多资料不见了

  • 造价通是不是出问题了 很多资料不见了
  • 0
  • 1
  • 不含税费 | 不含运费
  • 2009-03-28
查看价格

问题喷头DN40(含装饰罩)

  • -
  • 25个
  • 1
  • 胜捷
  • 中高档
  • 含税费 | 不含运费
  • 2017-03-29
查看价格

画出最大同心圆(二)

  • 投影机(直径1800mm)+感应摄像头
  • 1套
  • 1
  • 梦派
  • 中高档
  • 不含税费 | 含运费
  • 2022-10-12
查看价格

单结构最大需量仪表

  • 加强型 (双指针) 90° 型号:SD-72 外型尺寸:72×72
  • 10只
  • 1
  • 恒力
  • 中档
  • 不含税费 | 不含运费
  • 2015-10-29
查看价格

单结构最大需量仪表

  • 加强型 (双指针) 90° 型号:SD-96 外型尺寸:96×96
  • 9只
  • 1
  • 恒力
  • 中档
  • 含税费 | 不含运费
  • 2015-07-10
查看价格

最大子数列问题Kadane算法

Kadane算法扫描一次整个数列的所有数值,在每一个扫描点计算以该点数值为结束点的子数列的最大和(正数和)。该子数列由两部分组成:以前一个位置为结束点的最大子数列、该位置的数值。因为该算法用到了“最佳子结构”(以每个位置为终点的最大子数列都是基于其前一位置的最大子数列计算得出),该算法可看成动态规划的一个例子。

  • 给定一个数列,例如【−2, 1, −3, 4, −1, 2, 1, −5, 4】, 求一个连续的数列使得数列内的元素和最大, 示例中最大子数列应该是【4, −1, 2, 1】, 求和值为6。

  • 这个问题是可以衍生到一些变种问题, 如寻找数列中最大乘积序列,且要求序列中,相邻元素间隔不超过限定值等, 常出现在笔试面试编程题中。

  • 该问题最早于1977年提出,但是直到1984年才被Jay Kadane 发现了线性时间的最优解法,所以算法虽然长度很短,但其实并不容易理解。

  • 算法描述:

    • 遍历该数组, 在遍历过程中, 将遍历到的元素依次累加起来, 当累加结果小于或等于0时, 从下一个元素开始,重新开始累加。

    • 累加过程中, 要用一个变量(max_so_far)记录所获得过的最大值

    • 一次遍历之后, 变量 max_so_far 中存储的即为最大子片段的和值。

  • 此处为python 代码 , 变量A 传入数组。

  • 首先, 题目中有一个隐含的设定, 最大子片段是可以为空的, 空片段的和值是0。 这一点必须要明确, 不然会无法理解算法的正确性, 所以当给定的数列中,求和为负数的时候,例如【-2,1, -3】, 算法会返回最大求和值0, 因为默认该数组的最大子片段是一个空序列。

  • 理解此算法的关键在于:

    算法可用如下Python代码实现:

    defmax_subarray(A):max_ending_here=max_so_far=A[0]forxinA[1:]:max_ending_here=max(x,max_ending_here x)max_so_far=max(max_so_far,max_ending_here)returnmax_so_far
    

    该问题的一个变种是:如果数列中含有负数元素,允许返回长度为零的子数列。该问题可用如下代码解决:

    defmax_subarray(A):max_ending_here=max_so_far=0forxinA:max_ending_here=max(0,max_ending_here x)max_so_far=max(max_so_far,max_ending_here)returnmax_so_far
    

    这种算法稍作修改就可以记录最大子数列的起始位置。Kadane算法时间复杂度为O(n),空间复杂度为O(1)。

    查看详情

    最大子数列问题常见问题

    查看详情

    最大子数列问题文献

    联塑设立加拿大子公司 联塑设立加拿大子公司

    联塑设立加拿大子公司

    格式:pdf

    大小:63KB

    页数: 未知

    香港(2012年4月3日)中国最大的塑料管材制造商联塑集团正在扩大其业务,成立一个新的业务部门以生产塑料门窗等其他建材产品,并在加拿大设立子公司。这家总部位于广东顺德的企业在2011年报中宣布了

    联塑设立加拿大子公司 联塑设立加拿大子公司

    联塑设立加拿大子公司

    格式:pdf

    大小:63KB

    页数: 1页

    香港(2012年4月3日)中国最大的塑料管材制造商联塑集团正在扩大其业务,成立一个新的业务部门以生产塑料门窗等其他建材产品,并在加拿大设立子公司。

    建筑模数数列幅度

    第2.2.1条 水平基本模数应为1M。1M数列应按100mm进级,其幅度应由1M至20M。

    第2.2.2条 竖向基本模数应为1M。1M数列应按100mm进级,其幅度应由1M至36M。

    第2.2.3条 水平扩大模数的幅度,应符合下列规定:

    一、3M数列按300mm进级,其幅度应由3M至75M;

    二、6M数列按600mm进级,其幅度应由6M至96M;

    三、12M数列按1200mm进级,其幅度应由12M至120M;

    四、15M数列按1500mm进级,其幅度应由15M至120M;

    五、30M数列按3000mm进级,其幅度应由30M至360M;

    六、60M数列按6000mm进级,其幅度应由60M至360M等,必要时幅度不限制。

    第2.2.4条 竖向扩大模数的幅度,应符合下列规定:

    一、3M数列按300mm进级,幅度不限制;

    二、6M数列按600mm进级,幅度不限制。

    第2.2.5条 分模数的幅度,应符合下列规定:

    一、1/10M数列按10mm进级,其幅度应由1/10M至2M;

    二、1/5M数列按20mm进级,其幅度应由1/5M至4M;

    三、1/2M数列按50mm进级,其幅度应由1/2M至10M。

    第三节 模数数列的适用范围

    第2.3.1条 水平基本模数1M至20M的数列,应主要用于门窗洞口和构配件截面等处。

    第2.3.2条 竖向基本模数1M至36M的数列,应主要用于建筑物的层高、门窗洞口和构配件截面等处。

    第2.3.3条 水平扩大模数3M、6M、12M、15M、30M、60M的数列,应主要用于建筑物的开间或柱距、进深或跨度、构配件尺寸和门窗洞口等处。

    第2.3.4条 竖向扩大模数3M数列,应主要用于建筑物的高度、层高和门窗洞口等处。

    第2.3.5条 分模数1/10M、1/5M、1/2M的数列,应主用于缝隙、构造节点、构配件截面等处。

    分模数不应用于确定模数化网格的距离,但根据设计需要分模数可用于确定模数化网格平移的距离。

    查看详情

    阶数在递归数列中的定义

    递归数列: 一种用归纳方法给定的数列。

    递归数列举例:例如,等比数列可以用归纳方法来定义,先定义第一项 a1 的值( a1 ≠ 0 ),对 于以后的项 ,用递推公式an 1=qan (q≠0,n=1,2,…)给出定义。一般地,递归数列的前k项a1,a2,…,ak为已知数,从第k 1项起,由某一递推公式an k=f(an,an 1,…,an k-1) ( n=1,2,…)所确定。k称为递归数列的阶数。例如 ,已知 a1=1,a2=1,其余各项由公式an 1=an an-1(n=2,3,…)给定的数列是二阶递归数列。这是斐波那契数列,各项依次为 1 ,1 ,2 ,3,5 ,8 ,13 ,21 ,…,同样 ,由递归式an 1-an =an-an-1( a1,a2 为已知,n=2,3,… ) 给定的数列,也是二阶递归数列,这是等差数列。

    查看详情

    约束最优化问题约束最优化问题的解法

    约束最优化问题就是求目标函数

    满足约束条件
    的极值问题。因此,约束最优化,也称条件极值 。

    约束最优化问题的解法有两种:

    约束最优化问题化约束最优化问题为无约束最优化问题

    例1 最大面积 设长方形的长、宽之和等于

    问长方形的长、宽如何设计,才能使面积最大"para" label-module="para">

    解: 这就是一个约束最优化问题:设长方形的长为x,宽为y,求目标函数A=xy在条件x y=a之下的最大值。

    由于从约束条件x y=a中容易解出y=a-x,代入目标函数

    问题归结为求一元函数A(x)的极值。

    ,得驻点
    。这是实际问题,最值一定存在,则
    就是最大值点。因此,当
    时,长方形面积最大,其最大值为

    从上述例子可以看出化约束最优化问题为无约束最优化问题的思路:从约束条件

    中解出
    并将它代人目标函数
    于是,问题就转化为求一元函数

    的无约束最优化问题。

    但是,这种方法有局限性,因为有时从约束条件

    中解出y或x并非易事。因此,下面介绍另一种方法 。

    约束最优化问题拉格朗日乘数法

    这一方法的思路是:把求约束最优化问题转化为求无约束最优化问题,看它应该满足什么样的条件"para" label-module="para">

    是函数
    在约束条件
    下的约束最优化问题的极值点。如果函数
    在点(x,y)的邻域内有连续偏微商,且
    不全为0(不妨设
    ≠0),则根据费马引理,一元函数
    在点x的微商

    由隐微分法,有

    是由
    所确定,所以

    代入上式,消去
    ,得

    则有

    称满足此方程组(1)的点(x,y)为可能极值点。

    为了便于记忆,并能容易地写出方程组(1),我们构造一个函数

    为拉格朗日函数。则方程组(1)可以记为

    于是,我们把用拉格朗日乘数法求解约束最优化问题的步骤归纳如下:

    ①构造拉格朗日函数

    称为拉格朗日乘数;

    ②解方程组

    得点(x,y)为可能极值点;

    ③根据实际问题的性质,在可能极值点处求极值 。2100433B

    查看详情

    相关推荐

    立即注册
    免费服务热线: 400-888-9639