最大子序列和问题

  • A+
所属分类:算法与数据结构

问题

给定(可能有负数)整数序列A1, A2, A3..., An, 求这个序列中子序列和的最大值。

思考过程

一、最简单的实现

起点从0开始到数组最后一位元素,终点从起点开始到数组最后一位元素,即遍历所有情况,在遍历过程中,每加一个元素,就与maxSum进行比价,得到最大的和。

二、判断能否用动态规划求解

(此能力还有所欠缺)

多阶段决策最优解模型(在此过程中判断失误,按照上述最简单的思路,似乎没有在某个阶段决策的过程,其实不然)、最优子结构、无后效性、重复子问题。

可以将数组中每一元素的选择作为一个阶段,所以共有a.length个阶段。在每一阶段中,此元素有两种选择:

  1. 作为前面元素和的下一个元素,加入进去。
  2. 最为子序列的第一个元素。

三、回溯法求解

按照上述分析,用回溯求解。

四、画出状态转移图

最大子序列和问题

在画状态转移图过程中发现,maxSum会出现在每次分叉时,sum最大的一支上。即:

sum[i] = max(sum[i-1]+a[i], a[i])

代码:

本题来自leetcode53

解答如下:

 

许龙涛

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: