LeetCode＃891 子序列宽度之和

原题

给定一个整数数组 ，考虑 的所有非空子序列。

对于任意序列 S ，设 S 的宽度是 S 的最大元素和最小元素的差。

返回 A 的所有子序列的宽度之和。

由于答案可能非常大，请返回答案模 10^9+7。

示例：

这是第98场周赛上的最后一题，是比较难的。

代码模板：

思路

题目要求一个数组的所有子数组的最大最小值的差之和。

对 Python ，有内建的 函数用于求可迭代对象的最大元素。于是问题就只剩下如何获取 的所有子集，得到 的所有子集，然后将所有子集的“宽度”相加、 就行了。

对于求一个 的全部子集，有两种途径：

Python 标准库给出了现成的函数供调用：。

本题要用到 实际上是初始化了一个 对象，该对象是一个迭代器，示例如下：

这个迭代器的元素是 中两元素组合的所有情形组成的 。、

用递归或迭代等方法自己实现求得 子集的函数。

实现（思路1）

首先我们要写一个 函数来求一个整数数组的宽度（题中所述列表中最大最小元素之差）：

如上，7、8 两行即可实现，很简洁。

随后利用 对 进行迭代。由于 是指定元素个数的，我们使用两个 for 循环，第一个循环控制子集的长度，例如 ，则子集长度可能为 ；第二个循环就遍历特定长度的子集，比如 中写的 将遍历 这三个 。

代码：

测试

代码最后面再加几行测试，注意代码不缩进：

可见输出结果正确，但是耗时极长，无法通过LeetCode的测试，在 较长时此算法没有使用价值。不过想想也知道既然 是Python内建函数，想必已经在效率问题上做到几乎最好了吧，而967ms这一成绩所受限制是Python的基因。

实现（思路2）

自己实现求子集的函数，尽管效率很可能不如内建函数，但有重大的学习意义。这里仅简要讨论递归方法，若想深入研究或学习其他求子集算法可参考 CSDN博客：求一个集合所有子集的Python实现。

测试

答案正确，但所耗时长为思路1的两倍。