Roy Liang2020-10-20求乘积最大子数组空间复杂度优化： #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; }展开作者回复: 没有问题，通过滚动数组来优化空间复杂度。
1
子夜21042020-10-14这一讲好难，特别是不重叠的子数组之和。 从“这个时候我们需要再思考一下。对于原问题来说，其真正的最优解中最后一个子数组的最后一个元素，并不一定是 i 这个元素，有这么几种情况：”开始，感觉话锋一转，突然就不明白了。老师能对这句话再解释下吗？ 还有下面的几种情况，也不是很理解，能不能加个图解释下？ 1.舍弃第 i 个元素，将前 i−1 个元素划分为 j 个数组； 2.选取第 i 个元素，将前 i−1 个元素划分为 j 个数组；而当前元素加入第 j 个数组。在这种情况下有一个特殊要求，即第 i−1 个元素必须在第 j 个数组中，这样第 i 个元素才能加入进去；否则，不连续的元素不能放在一个子数组中（我们在计算子数组问题，前提就是要“连续”）； 3.选取第 i 个元素，将前 i−1 个元素划分为 j−1 个数组；而当前元素自己成为第 j 个数组。作者回复: 这句话的意思是DP[i][j] 表示将数组的前 i 个元素划分为 j 个子数组时的最优解，但是这个最优解里不一定包含第i个元素（也就是最大重叠子数组并没有选择第i个元素作为子数组的一部分），所以我们需要分情况来讨论。 至于下面的三种情况也就是最优解的三种情况： 1. 第i个元素并不在将前i个元素划分为j个子数组的最优解中，因此D[i][j]其实也就是DP[i-1][j] 2. 前i个元素划分为j个子数组的最优解中包含第i个元素，这个时候需要考虑两种情况。第一种情况是将前i-1个元素划分成了j个子数组，这个时候需要把第i个元素放到第j个子数组中，也就是原文中情况2。第二种情况是将前i-1个元素划分成j-1个子数组，第i个元素单独作为一个新的子数组，形成j个数组。
共 2 条评论1
我是一把火2020-10-13可以用变量替代数组来降低空间复杂度，因为每个子问题只依赖前一个子问题的结果： 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()两个函数的参数是相同的，本质上是做了重复计算，所以是否能用排序来代替..作者回复: 排序还需要先构造数组，然后做排序。由于这里只有三个元素，因此这样处理是合适的，可以不把简单的问题复杂化。
1
coder2023-08-03 来自北京#关于不重叠的子数组之和的难点思考# 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 个子数组的目的。展开作者回复: 专程前来给你点赞
Geek20142023-04-16 来自北京这一讲，最大子数组之和，这个题目dp[i][j] 和 M[i][j] 这两个备忘录的各自作用是啥，之间的联系是啥，貌似都没有讲的很清楚，理解起来，难度太大了。完全不明白什么意思？作者回复: 课程里有阐述： DP[i][j] 表示将数组的前 i 个元素划分为 j 个子数组时的最优解 M[i][j]表示将数组的前 i 个元素划分为 j 个子数组，并且第 i 个元素一定在第 j 个数组中时的最优解 由于DP[i][j]中求最优解时需要知道DP[i][j] 中的第 i 个元素一定在第 j 个数组中时的最优解，而DP[i][j]本身并没有这个性质，因此需要M[i][j]辅助求解DP[i][j]
Simon2022-05-18能直接这样写？ int dp_max[n], dp_min[n];作者回复: 是的，现在可以这样写。 C99和C++14标准之后支持变长数组（VLA），也就是支持用变量作为数组长度（gcc中的c++也早就支持这个扩展了），虽然C++14和C99的VLA语义不完全一致，不过现在的确是可以这样写的。
- alex_lai2022-02-07第一题示意图和代码不相符？ 不适合理解 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)
作者回复: 示意图和代码应该是相符的，文中，这里i表示的是元素，j表示子数组的数量。 至于你这里的状态需要考虑一下是否能够真的得到全局最优解。
共 2 条评论 - Geek_606c632021-09-20这个题目看了老半天才弄懂啥意思，第一个例子中k等于1时，输出答案是10才对
作者回复: 这里是笔误，输出的确是10，非常感谢。
猫头鹰爱拿铁2020-12-18感觉这一节突然变难了，关于不重叠子数组这为什么j是倒推的呢作者回复: 这里 其实j的计算顺序不会影响最后的结果，倒推或正推都是可以的
Jack2020-11-30已知一个无序数组，求该数组的一个连续子集，使得该连续子集的和的绝对值是所有连续子集中的绝对值最小的，请问这个可以用动规解决吗作者回复: 这个可以用动态规划解决，思路可以参照最大子数组之积的思路。