如何用DP降低到O(n)才是我们的目标,这才是算法的魅力所在,接下来,总结DP求解的思维过程。...2
分析一个数组,假定每一个元素都不小于0,如,[2, 3, 0 , 4], ok, 当子数组 [2],最大连乘为2,当子数组为[2,3],最大连乘可能的组合:3,2*3,最大子数组为:[2,3],如果标记...dp[0], dp[1] 计算正确,dp[2]错误,因为[-2,-3,-2] 的最大累乘为:(-3)*(-2) = 6....在哪里摔倒就在哪里爬起来,在计算dp[2]时,按照递推 max(a[2], a[2]*dp[1])计算时,a[2]*dp[1] = -12 ,如果我们再标记一个最小值,dpmin[i]表示为以i为索引的最小值...以上关键步骤,涉及到对第 i 个元素为负数时的处理过程,dp[i] 和 dpmin[i] 计算有怎样的依赖关系,当a[i] 为负数时,dp[i-1] * a[i] 变为最小,dpmin[i-1] * a