`
十三月的
  • 浏览: 168045 次
  • 性别: Icon_minigender_1
  • 来自: 长沙
社区版块
存档分类
最新评论

打破思维断层之最大子序列和

阅读更多

         最大子序列和

目的

本博客以求最大子序列和算法为载体,试图在减少思维断层的情况下解决问题。

目录:(以全新视角审视本问题)

      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;
	}

 多提意见.....

  • 大小: 6.3 KB
  • 大小: 13 KB
  • 大小: 17.7 KB
  • 大小: 10.1 KB
  • 大小: 10.2 KB
  • 大小: 9.8 KB
1
1
分享到:
评论
2 楼 十三月的 2013-04-18  
akandfxs 写道
[1,-2,3,5,-1,-1,  3]的最大子序列[3,5,-1,-1,3]

抱歉 写错了,已经改正
1 楼 akandfxs 2013-04-18  
[1,-2,3,5,-1,-1,  3]的最大子序列[3,5,-1,-1,3]

相关推荐

    cnn+biaoqian_断层识别_断层人工智能_断层_CNN

    在训练过程中,CNN会通过反向传播算法调整滤波器的权重,以最大化识别断层的能力。 在这个“cnn+biaoqian”项目中,我们可能首先进行了数据预处理,包括图像增强(例如旋转、缩放、翻转等)以增加模型的泛化能力,...

    Surfer8.0 做断层的方法

    在地质学、地理信息系统(GIS)以及地球科学领域中,断层的研究对于理解地壳结构、地震活动和地形演化至关重要。Surfer8.0是一款强大的科学绘图与数据分析软件,广泛应用于地球科学领域,能够创建高质量的三维表面...

    钱营孜煤矿过F22断层可行性研究

    钱营孜煤矿F22断层是井田内最大的正断层,为西二、西三采区边界断层。断层断距20~350 m,区内延伸长度6.50 km以上。根据钱营孜煤矿采区接替要求,接替的西三采区集中石门势必要穿越F22正断层。该断层落差大,延伸长,断层...

    3dmine断层建模

    通过精确的三维模型,矿业工程师可以更加直观地了解矿体和断层的实际情况,从而为矿产资源的高效和安全开采提供科学依据。随着矿业技术的不断进步,三维地质建模软件的作用将会越来越重要,3DMine等软件的开发和应用...

    综采工作面过断层方法

    综采工作面过断层方法是指在采煤过程中,采煤工作面遇到地质断层时所采取的过断层技术手段。由于断层的存在会破坏煤矿的地质...通过合理规划和精心施工,可以最大限度地减少断层对煤矿生产的影响,提高煤矿的经济效益。

    断层等值线绘制

    在给定的程序中,可能采用了特定的算法来处理断层,比如考虑到断层两侧的数据差异,可能会选择合适的权重分配给两侧的数据点,以确保等值线在断层处的连续性和合理性。此外,程序可能还提供了交互式功能,让用户能...

    基于MAPGIS的断层分形研究 基于MAPGIS的断层分形研究

    基于MAPGIS的断层分形研究,是一种将先进的信息技术与地质学紧密结合的创新研究方法,旨在深入探索断层系统的复杂性和规律性。断层,作为地球表面和地壳内部广泛存在的地质构造,其形态和分布呈现出高度的复杂性和不...

    SPECT图象的最大似然断层重建

    ### SPECT图像的最大似然断层重建 ...通过综合考虑统计模型和迭代算法,最大似然断层重建不仅能够显著提高图像质量,还能有效地补偿随机干扰、衰减和散射等因素的影响,为医学成像领域带来了革命性的进步。

    工作面揭露隐伏断层的识别及过断方法

    这里的沉积环境分析可能包括对岩层结构、沉积序列和岩石类型的研究,以了解是否存在与断层活动相关的迹象。而周边巷道情况的分析则涉及对开采面周边巷道的稳定性、岩层变化趋势的观察,以及对巷道内出现的异常现象...

    逆断层两盘构造煤成因机理与分布

    构造煤是煤矿瓦斯灾害防治和煤层气开发的重要研究内容之...研究表明,断层上盘为主动盘,下盘为被动盘,构造煤具有片状序列结构特点,而且主要形成在断层上盘一定宽度的范围内,构造煤的厚度和发育程度随着远离断层而减小。

    煤矿平面位移断层分析研究

    在探讨煤矿平面位移断层分析研究中,首先需要对平面位移断层的概念和特性有所了解。平面位移断层,又称平移断层,是指在地壳运动过程中,地层沿某一平面发生相对水平移动的一种断层。这种断层的特征在于断层面相对...

    断层模拟程序

    给定的文件描述了一个简单的断层模拟程序,旨在通过可视化的方式展示断层的形成与运动过程,为学术交流和技术探讨提供基础平台。 ### 核心知识点解析 #### 1. 断层简化模拟 断层简化模拟是指将复杂的地质断层简化...

    弱导水性断层防水煤柱的留设

    为了防止断层底板水突出,需保留...根据公式的来源与断层突水机理,讨论原计算公式的不合理性,认为公式中应加上反映断层导水性的断层破碎带宽度和屈服带宽度,在此基础上推导出新的断层防水煤柱留设宽度,并论证其合理性。

    顶板断层附近采动作用规律研究

    根据贵州某矿111013回采工作面的地质条件制作相似试验模型,模拟回采工作面从靠近到远离顶板断层过程。研究结果表明:随着回采工作面靠近断层,...当回采工作面位于顶板断层正下方时,断层面上的正应力和剪应力均达到极值。

    断层构造失稳突变诱发冲击地压机制研究

    当断层倾角为45°时,断层面上切应力和滑移量最大;断层切应力随断层切向刚度和侧压力系数的增加而增大;水平构造应力作用下,当工作面距前方断层30 m内,断层面上切应力最低。工作面过断层时对断层扰动极大,断层切应力...

    excel断层图表制作

    Excel断层图表是一种独特且富有视觉冲击力的数据...总的来说,Excel的断层图表是一种强大的数据分析工具,通过适当的步骤和调整,可以有效地呈现数据的变化和差异。熟练掌握这一技巧,将对你的数据分析能力大有裨益。

    煤矿井下过断层技术浅析

    煤矿井下过断层技术浅析涉及的主要知识点包括煤矿井下断层的成因、断层的影响、断层的识别方法以及煤矿井下采掘工作面过断层的技术方法和巷道支护方式。 首先,煤矿井下断层的成因是由于地质构造应力的作用,在地下...

    龙永煤田滑脱断层特征及其控煤作用

    二叠统栖霞组灰岩和童子岩组煤系间的F0断层;童子岩组煤系一段与三段直接的F01断层;童子岩组煤系与上二叠统屏山组之间的F02断层;翠屏山组与下三叠统溪口组的F03断层等滑脱断层。龙永煤田滑脱断层的成因机制为:在晚古...

    断层对工作面底板突水的影响机理研究

    如图1所示,断层的力学模型考虑了断层的倾角α、最大应力σ1和最小应力σ2等因素。通过剪切应力τ1和正面应力σ的计算,结合岩层的摩擦角β和侧压系数φ,可以判断断层是否处于活化状态。当剪切应力τ1大于或等于...

Global site tag (gtag.js) - Google Analytics