这道题Brute Force的做法很好想，我们可以枚举所有的最大最小值min/max，然后找出在[min, max]范围的的数字，假设有m个，那么以min和max为最小最大值的子序列一共有2^m，对于这一组的总宽度就为2^m * (max - min)。假设输入数组长度为n，所有枚举的可能有n^2，每一次找出在[min, max]范围的数需要O(n)，总的时间复杂度为O(n^3)。
显然暴力的方法时间复杂度太高了，我们需要尝试优化一下。一个可行的思路就是sort，排序并不会对结果产生任何影响，而且我们在寻找落在[min, max]中的数的个数用binary search即可，这样的话时间复杂度可以提升到O(n^2 * log n)。
另外一种方法是运用DP的思路，如果我们从小到大考虑所有的数，如果我们用dp[i]表示以A[i]结尾的所有subsequences的width，我们可以得到递推公式：
- dp[i] = sum(dp[j] + (A[i] - A[j]) * k[j])，其中k[j]代表以A[j]结尾的子序列的个数，0 <= j <= i
这个很好理解，因为对于以A[j]结尾的子序列，其后面添加一个A[i]可以形成一个新的子序列，而这个子序列的width就是在原先的基础上加上A[i] - A[j]，如果有k[j]个以A[j]结尾的子序列，那么总宽度就会变为dp[j] + (A[i] - A[j]) * k[j]。那么dp[i]就是遍历所有可能的j求和。那么选择问题就是如何求k[j]，这个其实很好求，首先A[j]是固定的，那么每个[A[0], A[1]....A[j - 1]]的子集就可以形成一个独特的子序列，所有有2^j个子序列。这里要注意一点是输入数组可能很长，那么2^j可能越界，所以我们需要提前求出取余之后对应的值，存在数组k中。这个方法的时间复杂度为O(n^2)，空间复杂度O(n)。代码如下：
但是这个方法时间复杂度仍然较高，过不了比较变态的test case。所以我们还需要更有效率的方法。根据暴力的解法，最后的结果可以表示为sum((A[j] - A[i]) * 2(j - i - 1))，0 <= i < j < n。展开之后为:
- 2^0 * A[1] + (2^0 + 2^1) * A[2] + (2^0 + 2^1 + 2^2) * A[3] + ... + (2^0 + 2^1 + ... + 2^(n - 2)) * A[n - 1]
- (2^0 + 2^1 + ... + 2^(n - 2)) * A[0] + ... + (2^0 + 2^1) * A[n - 3] + 2^0 * A[n - 2]
展开始之后就为上面两项的差(第一项减去第二项)，上面两项又可以表示为：
- sum((2^j - 1) * A[j]), where 0 < j <= n - 1
- sum((2^(n - 1 - i)) * A[i]), where 0 <= i < n - 1
所以我们只需要遍历一遍就可以把上面两项求出来，那么时间复杂度就可以缩短到O(n * log n)，就是排序的时间复杂度。代码如下：
No comments:
Post a Comment