最大子序列和
目的:
本博客以求最大子序列和算法为载体,试图在减少思维断层的情况下解决问题。
目录:(以全新视角审视本问题)
1)问题阐述
2)问题本质
3)代码实现
第一步:问题阐述
一个有N个元素的整型数组A,有正有负,数组中连续一个或多个元素组成一个子数组,这个数组有很多子数组,求子数组之和的最大值。
例如:[1,-2,3,5,-1,-1, 3]的最大子序列[3,5,-1,-1,3].
[-9,-2,-3,-5,-3, -1]的最大子序列[-1]
(注:定义中要求的是连续的,其实这个问题的名称很不称职,“子序列”这个名字其实意味着并不要求各个元素相连,像最长公共子序列(LCS)问题中一样,并没有要求连续。所以这个问题另外一个名字较好:最大字数组和。)
第二步:问题本质
下面我们来想一下这个问题,也许最简单的办法就是把所有的子数组全部求出来,然后比较选出最大的一个。
相信网上有很多代码实现,最差的o(n3) ,优化过后可以是o(n2).(优化的依据是找出最大的,并不需要保存所有的子数组),最优美的应该是动态规划方法。但是通过分析问题知道此问题确实包含最优子结构和重叠子问题,但是实现起来还是有些困难,总觉的有些东西没想明白,于是仔细分析该问题的本质之后才豁然开朗。
下面来分析此问题的本质:用图片表示
单纯的看这个简单的题目,也许很多人能够直接给出答案最大字数组和是8即3+5.如果数组元素很多,事情就难办了,这个问题最好状态下时间复杂度是多少呢?是o(n)
原因在于:本例中我们先是算出[1,1] = 1, [1,2] = 3,[1,3] = -1.事情就在这里发生了转折,因为我知道,下一步很多子数组已经被淘汰了,无需计算。这些无需计算的字数组是前3列。为什么呢?
之后我们分别计算了[4,4],[4,5]和[4,6]
这样我们就真的做到了o(n)
其实很多博客提到了全是负数的情况,我们举例证明
最大值是:-1,时间复杂度仍旧是o(n)
第三步:代码实现
上述分析如何用代码迅速实现呢?还是以上面例子分析
开始我们计算[1,1],[1,2],[1,3]这个可以使用两个指针i和j 。i和j开始同时指向1,i不变,j不断增加,当增加到3的时候,发现总的大小小于0,此时意味着j不需要在增大为4,5,6(第一列无需再计算) i重新赋值为j+1 =4 (前j列不需再计算)
/** * 最大子序列和 * @param data * @return */ public static int maxSubarray(int[] data) { //保存真正最大子序列和的起始位置 int start = 0; int end = 0; //最大值 int max = Integer.MIN_VALUE; //当前序列起始位置和最大值 int currentStart = 0; int currentEnd = 0; int currentMax = 0; // for (int i = 0; i < data.length; i++) { currentMax += data[i]; //判断当前是否大于0 if (currentMax >= 0) { currentEnd = i; if (currentMax > max) { max = currentMax; start = currentStart; end = currentEnd; } } else { currentMax = 0; currentStart = i + 1; currentEnd = i + 1; } } //打印结果 for (int i = start; i <= end; i++) { System.out.println("i = " + i + " " + data[i]); } System.out.println("max = " + max); return max; }
多提意见.....
相关推荐
钱营孜煤矿F22断层是井田内最大的正断层,为西二、西三采区边界断层。断层断距20~350 m,区内延伸长度6.50 km以上。根据钱营孜煤矿采区接替要求,接替的西三采区集中石门势必要穿越F22正断层。该断层落差大,延伸长,断层...
为了研究断层附近矿井突水事故的发生机理,利用有限差分数值模拟软件FLAC3D模拟分析不同倾角的断层在采掘扰动影响下的地应力场和塑性区情况。结果表明:断层倾角越大,断层面上的剪应力和法向应力越大;采掘处以深断层...
构造煤是煤矿瓦斯灾害防治和煤层气开发的重要研究内容之...研究表明,断层上盘为主动盘,下盘为被动盘,构造煤具有片状序列结构特点,而且主要形成在断层上盘一定宽度的范围内,构造煤的厚度和发育程度随着远离断层而减小。
为了防止断层底板水突出,需保留...根据公式的来源与断层突水机理,讨论原计算公式的不合理性,认为公式中应加上反映断层导水性的断层破碎带宽度和屈服带宽度,在此基础上推导出新的断层防水煤柱留设宽度,并论证其合理性。
为准确掌握小断层的延伸规律,降低小断层对矿井采掘活动的影响,以王家塔井田3-1煤层在采掘活动中揭露的小断层资料为依据,选取断层走向延展长度、断层落差和断层倾角3个因素,采用多元线性回归的方法,分别建立NE向和NW...
断层是一个难点,怎么做呢,这里是一个断层实例做的方法,初手就跳过,中级人员仔细看好了。
根据贵州某矿111013回采工作面的地质条件制作相似试验模型,模拟回采工作面从靠近到远离顶板断层过程。研究结果表明:随着回采工作面靠近断层,...当回采工作面位于顶板断层正下方时,断层面上的正应力和剪应力均达到极值。
当断层倾角为45°时,断层面上切应力和滑移量最大;断层切应力随断层切向刚度和侧压力系数的增加而增大;水平构造应力作用下,当工作面距前方断层30 m内,断层面上切应力最低。工作面过断层时对断层扰动极大,断层切应力...
二叠统栖霞组灰岩和童子岩组煤系间的F0断层;童子岩组煤系一段与三段直接的F01断层;童子岩组煤系与上二叠统屏山组之间的F02断层;翠屏山组与下三叠统溪口组的F03断层等滑脱断层。龙永煤田滑脱断层的成因机制为:在晚古...
查明不同倾角正断层附近应力分布规律对瓦斯分布规律预测、煤与瓦斯突出预测具有重要的参考...煤厚和工作面距断层距离对断层附近横向上应力变化有重要影响,断层垂向高度和断层倾角对断层附近纵向上应力变化有重要影响。
断层突水是煤矿典型的动力灾害,是煤岩体在采动和承压水共同作用下失稳破坏过程。论文针对导水断层缩短了煤层和含水层距离特点,建立了断层突水的关键路径力学模型。将极限平衡理论和尖点突变理论引入断层突水分析,...
利用FLAC3D的强大数值模拟计算能力,以义马矿区为背景,建立了逆断层的简化数值模型,研究了不同断层倾角条件下的工作面超前支承压力与弹性能分布规律。研究表明:随着采掘面不断临近断层,工作面超前支承压力受断层影响...
为了安全高效地采出煤炭资源,采用FLAC3D数值模拟手段,研究了采动条件对断层的影响,分析了工作面采动断层活化特征进行,然后建立数值模型,对断层尖灭部位两盘沿垂直断面和断层面的位移动态变化规律进行了研究。...
断层防水煤(岩)柱宽度留设涉及到许多因素,也是许多学者和工程技术人员研究的重点之一。截止到目前已有多种研究方法与手段得到了应用,主要包括理论计算、多元回归分析、BP和RBF、相似模拟、数值模拟等,针对不同...
人工智能断层识别以及一部分标签制作流程,采用一般的卷积神经网络。
为了对矿区断层构造复杂度进行更加合理地评价,需要对断层多元信息进行综合分析。以徐州某煤矿为例,分析了断层的分形维数、落差及倾角等因素与矿井突水点涌水量的相关关系,建立断层信息与涌水量回归模型,通过Arc GIS...
3dmine断层建模研究,为矿山建立更贴近实际的矿体模型起到很好的作用!
以庚20煤层为例,对小断层发育特征进行了研究,认为区内小断层以正断层为主,井田东部小断层发育,断层密度大,其发育影响因素主要有两个:一是由大中型断层派生和伴生的,二是由于区域构造应力作用的不均匀性和岩石力学...
采用RFPA2D-Flow软件分析了含隐伏小断层底板在工作面开采中,底板岩层破坏、突水通道的形成及突水发生的整个动态发展过程,得到了开采过程中底板岩层裂隙的产生和扩展演化、损伤破坏区域的形成过程及渗流场的运移过程...
excel断层图表制作,教你如何使用excel断层图表制作