最大子序列和问题有哪些

 时间:2024-10-12 00:26:13

最大子序列和也叫数列的连续最大和,顾名思义,就是在一个长度为n的数列{An}中,求i,j(1<=i<=j<=n),使得数列{An}中,第i个元素到第j个元素之间,所有元素的和最大。例如:-2,11,-4,13,-5,-2时答案为20(11-413)。

最大子序列和问题有哪些

在这一遍扫描数组当中,从左到右记录当前子序列的和ThisSum,若这个和不断增加,那么最大子序列的和MaxSum也不断增加(不断更新MaxSum)。如果往前扫描中遇到负数,那么当前子序列的和将会减小。此时ThisSum 将会小于MaxSum,当然MaxSum也就不更新。

如果ThisSum降到0时,说明前面已经扫描的那一段就可以抛弃了,这时将ThisSum置为0。然后,ThisSum将从后面开始将这个子段进行分析,若有比当前MaxSum大的子段,继续更新MaxSum。

  • crc生成多项式怎么算?
  • 编程中提到的IDE是什么意思
  • 异或运算怎么算?
  • 创建视图的sql语句
  • Python如何查看已经安装的库
  • 热门搜索
    蓝莓怎么洗才干净 石斛怎么读 草鱼怎么做好吃 怎么在手机上赚钱 牛骨汤的做法大全 页码怎么设置 个人鉴定怎么写 素馅饺子的做法 58同城怎么发布信息 胃胀痛是怎么回事