contiguousSubsequences.md

连续性

比如求一个数组的最大连续子乘

例子： 1 2 -9 5 0 8

解法一：递归

func a(nums []int)int{
    // 设置return的最后边界

    // 设置运行过程 这个题就是这个数字用或者不用
    **重要：---> ***//用的话就是一直连续了， 不用那么就是不连续了，只需要将下一个 * 1 就可以不连续了

    // trill down 也就是往下一个递归走
}

解法二：动态规划

动态规划最重要的是定义一个状态转移方程，也就是说这一次的方程用上一个的状态能推导出来

这里就是 dp[i] 表示：从0初始位置到i位置的最大的值，dp转移方程为 dp[i]= max(do[i-1] *nums[i],nums[i]) 但是我们不知道

假如没有负数这就是OK，但是有负数就不一样了 如果是负数那么负数乘以负数就是正数，所以我们需要扩展为二维 来规定一个最大值和最小值

dp[i][0] = max(dp[i-1][0]*nums[i],dp[i-1][1]*nums[i],nums[i])
dp[i][1] = min(dp[i-1][0]*nums[i],dp[i-1][1]*nums[i],nums[i])

这里的跟nums[i]对比的意思就是抛弃了之前的值只保留这次的值说白了还是 从头开始

然后我们再让最大值跟一个指针对比，每次都获取到最大的那个值赋值给指针即可。

所以说动态规划最最最重要的就是动态转移方程。

再比如斐波那契数列： 动态转移方程就是 dp[i] = dp[i-1]+ dp[i-2]

很多的方程都是 dp[i]= max(dp[i-1],dp[i-2])