动态规划之最大子段和问题

城市轨道交通规划是解决城市交通问题的有效手段之一 #生活知识# #社会生活# #城市规划#

问题描述：
给定由n个整数（包含负整数）组成的序列a1,a2,...,an，求该序列子段和的最大值。

当所有整数均为负值时定义其最大子段和为0。
依此定义，所求的最优值为：

  例如，当(a1,a2 , a3 , a4 , a5 ,a6)=(-2,11,-4,13,-5,-2)时，

最大子段和为：

11+（-4）+13 =20
1、最大子段和问题的简单算法：

代码：

此算法的时间复杂度：O(n3)。

可对此算法进行适当改进，使其时间复杂度变为：O(n2)。

代码：

2、最大子段和问题的分治法：

代码：

//最大子段和，分治算法。T(n)=O(nlog(n))。

3 最大子段和问题的动态规划算法：

代码：

//最大子段和，动态规划，T(n)=O(n)。

网址：动态规划之最大子段和问题 https://www.yuejiaxmz.com/news/view/120610

相关内容

RL笔记：动态规划(1): 策略估计和策略提升
浅谈大学生活和职业生涯规划
我的大学生活和职业规划
当代生态环境问题论文（精选10篇）
动态规划特训：旅行商问题（回溯法或记忆搜索法）
职业生涯规划书最新
手把手教你强化学习 (四)动态规划与策略迭代、值迭代
生涯规划之时间管理妙招
人生职业规划(大全9篇)
应届生面试攻略丨被问职业规划，这样回答最加分

随便看看