12｜动态规划新问题2：攻破最大子数组问题

求乘积最大子数组空间复杂度优化： #include <iostream> using namespace std; int main() { int n, i, maxn, pre_max, pre_min, cur_max, cur_min; int a[10000]; cin >> n; for (i = 0; i < n; i++) { cin >> a[i]; } maxn = pre_max = pre_min = a[0]; for (i = 1; i < n; i++) { if (a[i] == 0) { cur_max = cur_min = 0; } else if (a[i] > 0) { cur_max = pre_max > 0 ? pre_max * a[i] : a[i]; cur_min = pre_min >= 0 ? a[i] : pre_min * a[i]; } else { cur_max = pre_min < 0 ? pre_min * a[i] : a[i]; cur_min = pre_max <= 0 ? a[i] : pre_max * a[i]; } maxn = max(cur_max, maxn); pre_max = cur_max; pre_min = cur_min; cout << "--> (" << cur_min << ", " << cur_max << ")" << endl; } cout << maxn << endl; }

这一讲好难，特别是不重叠的子数组之和。 从“这个时候我们需要再思考一下。对于原问题来说，其真正的最优解中最后一个子数组的最后一个元素，并不一定是 i 这个元素，有这么几种情况：”开始，感觉话锋一转，突然就不明白了。老师能对这句话再解释下吗？ 还有下面的几种情况，也不是很理解，能不能加个图解释下？ 1.舍弃第 i 个元素，将前 i−1 个元素划分为 j 个数组； 2.选取第 i 个元素，将前 i−1 个元素划分为 j 个数组；而当前元素加入第 j 个数组。在这种情况下有一个特殊要求，即第 i−1 个元素必须在第 j 个数组中，这样第 i 个元素才能加入进去；否则，不连续的元素不能放在一个子数组中（我们在计算子数组问题，前提就是要“连续”）； 3.选取第 i 个元素，将前 i−1 个元素划分为 j−1 个数组；而当前元素自己成为第 j 个数组。

可以用变量替代数组来降低空间复杂度，因为每个子问题只依赖前一个子问题的结果： def getMaxProduct(nums): ans = _max = _min = nums[0] for i in range(1, len(nums)): _max = max(_max * nums[i], _min * nums[i], nums[i]) _min = min(_max * nums[i], _min * nums[i], nums[i]) ans = max(ans, _max) return ans 时间复杂度的话，目前已经是O(n)了。不过注意到代码中max()、min()两个函数的参数是相同的，本质上是做了重复计算，所以是否能用排序来代替..

#关于不重叠的子数组之和的难点思考# dp方程的推导解释： DP[i][j] 表示将数组的前 i 个元素划分为 j 个子数组时的最优解。 状态初始化： (1) 一般对于二维备忘录，都需要对DP[0][j] 和 DP[i][0] 进行初始化。这里进行了相同的操作。对于两个维度的长度，分别比n和k大1，原因就是为了给DP[0][j] 和 DP[i][0] 进行初始化，并且用来做dp状态推导的边界。这样造成了 DP[i][j] 中的 i 的取值范围比nums的长度 n 多1，所以推导过程中的 DP[i][j] 实际上对应着 nums[i-1] 。 (2) DP[i][j] 中，当 i === j 的时候，意味着数组中每一个元素都组成一个子数组，最终导致 DP[i][j] 的结果就是对 nums 在范围 [0, i-1] 内求和。也可以在前一个 i === j 的基础上，加上当前值 nums[i-1] 。 (3) 其它的地方初始化成0，在定义备忘录的时候就可以初始化好。 (4) 当 j > i 的时候，返回的肯定是0。因为无法用较少的元素组合出较多的子数组。可以在第二层循环的时候，规避掉计算，从而达到如果一定要计算相同的情况，就走第三步的默认值。 状态方程的推导： DP[i][j] 的来源： (1) DP[i-1][j] : 代表着当前元素 nums[i-1] 不需要加入最优解，所以取上一次可以组合出 j 子数组的最优解即可； (2) DP[i-1][j] + nums[i-1] ，代表着当前元素 nums[i-1] 加入会更大。但是这里有个问题，因为 DP[i-1][j] 表示已经组合出 j 个子数组了，如果想加入 nums[i-1] ，必须保证 nums[i-2] 被包括在 DP[i-1][j] 之内。但是 DP[i-1][j] 的定义，并不能保证 nums[i-2] 被包括在内了，所以还需要第二个二维数组 M[i][j] 来记录末尾元素包含在内的最优解。M[i][j] 代表当前元素 nums[i-1] 必须包括在内的最优解（但不一定是整个题的最优解，仅仅辅助用）。所以这个位置的推导转化成 M[i][j] 。 M[i][j] 的来源： (1) M[i-1][j] + nums[i-1]：上一个组合成 j 个数组的M的解，加上当前值。因为M代表着一定包含着末尾元素，所以即使已经有 j 个子数组，仍然可以通过连接 nums[i-1] 而不增加 j 的数量。 (2) DP[i-1][j-1] + nums[i-1]：前 i-1 个元素（实际上对应到nums的范围是[0, i-2] ）组合成 j-1 个子数组的最优解，并加上当前值。虽然DP不能保证一定包含最后一个元素（从而能和 nums[i-1] 能连续上），但是因为组合的数组的数量只是 j-1，也没有到 j ，所以兜底的方案可以让 nums[i-1] 自成一个数组（实际上也必须是这样），而凑成 j 个子数组的目的。

这一讲，最大子数组之和，这个题目dp[i][j] 和 M[i][j] 这两个备忘录的各自作用是啥，之间的联系是啥，貌似都没有讲的很清楚，理解起来，难度太大了。完全不明白什么意思？

能直接这样写？ int dp_max[n], dp_min[n];

第一题示意图和代码不相符？ 不适合理解 Dp[i][j] i 是行数表示用了多少个子数组，上限为k j表示取第几个数 为什么需要第二个数组？ 不能优化一下加一个变量 boolean isIncludePrevious在内层循环里 表示j-1在第i个数组被include or not。 如果include==true在计算第j个数的时候可以 nums[j]可以叠加dp[i,j-1] 所以我的状态会是 Dp[i,j] = max( dp[i-1][j-1] + nums[j], Dp[i, j-1] when isIncludePrev==false, Dp[i, j-1] + nums[j] when isIncludePrev ==true)

这个题目看了老半天才弄懂啥意思，第一个例子中k等于1时，输出答案是10才对

感觉这一节突然变难了，关于不重叠子数组这为什么j是倒推的呢

已知一个无序数组，求该数组的一个连续子集，使得该连续子集的和的绝对值是所有连续子集中的绝对值最小的，请问这个可以用动规解决吗