题目本身很容易看明白,简单来说就是求最大值,求什么最大值呢?求子数组的最大值
我们以往的状态表示就是根据两点1.经验,2题目要求
我们通常以一个位置结尾来研究问题,所以,这次我们还是这样做。
创建一个dp表,dp[i]表示以i位置为结尾的子数组的最大值。
如图所示,假设i就在此位置,在所有的子数组中,大概分为两类,一种是长度大于1,一种是长度为1。
所以,仔细观察,我们不难发现
我们看,当i=0时,i-1=-1,就会越界,没法整,所以我们可以先将nums[0]初始化出来。
由大到小依次填表
返回dp[i]。