动态规划之最大子数组和问题

一.题目解析

题目本身很容易看明白，简单来说就是求最大值，求什么最大值呢？求子数组的最大值

二.讲解算法原理

1.状态表示

我们以往的状态表示就是根据两点1.经验，2题目要求

我们通常以一个位置结尾来研究问题，所以，这次我们还是这样做。

创建一个dp表，dp[i]表示以i位置为结尾的子数组的最大值。

2.状态转移方程

如图所示，假设i就在此位置，在所有的子数组中，大概分为两类，一种是长度大于1，一种是长度为1。

所以，仔细观察，我们不难发现

3.初始化

我们看，当i=0时，i-1=-1，就会越界，没法整，所以我们可以先将nums[0]初始化出来。

4.填表顺序

由大到小依次填表

5.返回值

返回dp[i]。

三.代码实现