`
deepnighttwo
  • 浏览: 49411 次
  • 性别: Icon_minigender_1
  • 来自: 上海
社区版块
存档分类
最新评论

大学时候想的一个算法——计算数组中最大和序列

 
阅读更多
本文与java语言无关,纯粹就是个解决问题的想法

问题:给定一个数组,要求求出数组中连续数和最大的索引对。比如,给定一个数组,里面有正数有负数和0。其中肯定有一个连续的序列(连续的,中间不能间断),比如说是索引3到索引5,这个序列的和是这个数组中连续序列中最大的,别的都没这个大。
{0,2.-1,9,7.6,-8,16},这个数组中就是索引三到索引五这个连续序列的和最大。要求算法的时间复杂度问O(n)。

问题解决:如果时间复杂度要求是O(n³)或者是O(n平方),就没意思了,直接循环搞定。

O(n)的时间复杂度如何解决:

注意,因为整个数组可能都是负数,这时候问题就退化成寻找数列中最大的负数了。首先,针对这种情况进行处理,将数组进行一次循环,找出第一个非负数索引和最后一个非负数索引,这个可以在一次循环中完成,如果 1)没找到,说明数组中全是负数,泽跳出循环,进行下一轮循环,寻找最大负数 2)如果两者相等,说明数组中只有一个正数,直接返回索引对 3)如果两者不等,则是相对复杂的情况,下面进行处理,到现在位置,时间复杂度是O(n),因为之循环了一次。

1:将数组的第一个非负索引和最后一个非负索引之间的连续的正数和连续的负数相加。比如{0,2.-1,9,7.6,-8,16},处理完后就应该得到数组{2, -1, 22, -8, 16}。这样整个数组就肯定是一个正负相间的数组。而且开头和结尾肯定是非负数。在进行处理的时候,还要维护一个大小是结果两倍的数组,用来存储每个元素的原来序列数值,比如,对于上面的数组,这个序列数组就应该是{0,1,2,2,3,5,6,6,7},这个数组是数组index,其中0,1是第一个元素在原来数组中的序列,2,2 是第二个元素在原来数组中的序列,3,5是第三个元素在原数组中的序列,依此类推。本步骤的时间复杂度也是O(n),没有循环嵌套,空间复杂度是O(2n)

2:现在得到一个正负相间的数组,而且数组中开头结尾都是非负数,而且数组中没个元素在原始数组中的索引序列对都是知道的。然后:
int start = 0;
int end = 0;
int count = 0;
对这个数组进行一次循环,循环中:
count += 数组[i]
if(count > 0){
将count的索引对(start, end)放入数组A中
将count的数值放入数组B中
} else{
count = 0;
}
这个循环时间复杂度是O(n),空间复杂度O(2n)
循环结束后,要的结果就在数组A和数组B中,遍历数组B找到最大的元素,然后根据最大元素的索引去A中找出索引对,然后根据这个索引对去前面的数组index找出结果。时间复杂度O(n)


整个算法看下来,时间复杂度就是O(n),进行了4次O(n)的循环,空间复杂度比较大一些,最大可能需要原来数组大小五倍的存储空间才能完成整个计算。





分享到:
评论

相关推荐

    算法实验——包括了排序、最长公共子序列等一系列算法

    这是一个有关算法的压缩包,里面包含二分算法、合并排序、最长公共子序列、最优装载、活动安排算法

    最长公共子序列实验报告

    运用动态规划算法解决最长公共子序列问题,计算最长公共子序列长度的动态规划算法LCS_LENGTH(X,Y)以序列X=, x2, …, xm>和Y=, y2, …, yn>作为输入。输出两个数组c[0..m ,0..n]和b[1..m ,1..n]。其中c[i,j]存储Xi与...

    论文研究-双序列比对的算法研究.pdf

    详尽分析了双序列比对的实际意义,提出最佳比对不一定能反映进化的实际过程并给予分析,重点探讨了最重要的全局比对算法——Smith Waterman算法,同时提出了一种用数组记录比对过程中遍历路径的方法并对比对过程进行...

    线性时间选择算法(附完整的代码,结合例题详细解析) 全套资源已打包好,求抱走!!!

    给定一个包含n个元素的一维线性序列a[p:r],从这n个元素中找出第k小的元素,1。设a[0:14]={2,9,11,3,14,7,10,8,15,4,13,1,6,5,12},k = 8,采用线性时间选择算法解决该问题。 1)写出算法实现代码并截屏程序运行结果...

    数据结构算法

    字符串相似度 经典算法题每日演练——第四题 最长公共子序列 经典算法题每日演练——第三题 猴子吃桃 经典算法题每日演练——第二题 五家共井 经典算法题每日演练——第一题 百钱买百鸡 开发利器系列(1)介绍一个小...

    算法笔试题:(Python实现)—— 算法面试题汇总

    II实现 Trie (前缀树)单词搜索 II有效的字母异位词字符串中的第一个唯一字符数组Python实现乘积最大子序列多数元素存在重复元素移动零打乱数组两个数组的交集 II递增的三元子序列搜索二维矩阵 II除自身以外数组的...

    c语言数据结构算法演示(Windows版)

    本课件是一个动态演示数据结构算法执行过程的辅助教学软件, 它可适应读者对算法的输入数据和过程执行的控制方式的不同需求, 在计算机的屏幕上显示算法执行过程中数据的逻辑结构或存储结构的变化状况或递归算法执行...

    C#全能速查宝典

    《C#全能速查宝典》共分为8章,分别介绍了C#语言基础、Windows窗体及常用控件、Windows高级控件、控件公共属性、方法及事件、数据库开发、文件、数据流与注册表...,共包含562个C#编程中常用的属性、方法、类和各种技术...

    数据结构与算法分析

     Mark Allen Weiss,1987年在普林斯顿大学获得计算机科学博士学位,师从著名算法大师Robert Sedgewick,现任美国佛罗里达国际大学计算与信息科学学院教授。他曾经担任全美AP(Advanced Placement)考试计算机学科...

    数据结构实验三(循环队列基本操作)题目和源程序

    1.任意输入队列长度和队列中的元素值,构造一个顺序循环队列,对其进行清空、插入新元素、返回队头元素以及删除队头元素操作。 2.约瑟夫环的实现:设有n个人围坐在圆桌周围,现从某个位置 i 上的人开始报数,数到 ...

    java源码包2

    在有状态SessionBean中,用累加器,以对话状态存储起来,创建EJB对象,并将当前的计数器初始化,调用每一个EJB对象的count()方法,保证Bean正常被激活和钝化,EJB对象是用完毕,从内存中清除…… Java Socket 聊天...

    数据结构与算法分析第二版 ---C语言描述(附加答案)

    算法分析2.1 数学基础2.2 模型2.3 要分析的问题2.4 运行时间计算2.4.1 一个简单的例子2.4.2 一般法则2.4.3 最大子序列和问题的解2.4.4 运行时间中的对数2.4.5 检验你的分析2.4.6 分析结果的准确性总结练习第3章 ...

    OpenSAL1.1算法导论开源算法库

    OpenSAL1.1 包含了算法导论中所有数据结构和算法以及其他内容,本资源为该算法库的静态链接库 内容如下(*号表示1.1版本新增内容): 数据结构:一般堆、二项堆、斐波那契堆、红黑树、通用散列(采用全域散列和完全...

    计算机二级公共基础知识

    数据的逻辑结构是对数据元素之间的逻辑关系的描述,它可以用一个数据元素的集合和定义在此集合中的若干关系来表示。数据的逻辑结构有两个要素:一是数据元素的集合,通常记为D;二是D上的关系,它反映了数据元素之间...

    数据结构与算法分析_Java语言描述(第2版)

    《数据结构与算法分析:Java语言描述(第2版)》是国外数据结构与算法分析方面的经典教材,使用卓越的Java编程语言作为实现工具讨论了数据结构(组织大量数据的方法)和算法分析(对算法运行时间的估计)。...

    双指针+前缀和算法刷题路线

    https://blog.csdn.net/congfen214/article/details/129926899因为这里提及到了二维这个词,所以我们先来定义一个二维数组s[][] , s[i][j] 表示二维数组中,左上角(1, 1)到右下角(i, j)所包围的矩阵元素的和。...

    数据结构与算法分析C描述第三版

    Mark Allen Weiss,1987年在普林斯顿大学获得计算机科学博士学位,师从著名算法大师Robert Sedgewick,现任美国佛罗里达国际大学计算与信息科学学院教授。他曾经担任全美AP(Advanced Placement)考试计算机学科委员...

    leetcode最难-algorithms:编码面试人员

    leetcode最难最难 ...弗洛伊德兔龟算法——周期检测 回溯问题 数独解算器 词搜索 皇后区 ... 所有 DP - 将问题减少到其他可解决的问题 + 记忆 优先队列 K路合并 最长回文子串问题方法 最多删除一个数字

Global site tag (gtag.js) - Google Analytics