最大子序列和问题有哪些

 时间: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如何查看已经安装的库
  • 热门搜索
    怎么去除马赛克 蒜蓉小龙虾怎么做 社保卡密码忘了怎么办 十万个为什么 微信怎么建群 万力轮胎怎么样 鬯怎么读 富贵包怎么形成的有什么危害 涟漪怎么读 陈赫为什么离婚