2019-10-14 17:00:10
问题描述：
问题求解：
如果暴力求解，时间复杂度是exponational的，因为这里是子序列而不是子数组。显然，直接枚举子序列是不太现实的了，那么可以怎么做呢？
切入点有两点：
1）数组的顺序对最后的结果是没有影响的，那么排序后的数组和原来的数组的结果是同样的，我们可以对原数组进行排序操作降低问题复杂性。
2）既然直接考虑序列的方案是不可行的，那么还有个思路就是去考虑每个数对最后结果的贡献。如果能想到这一点的话，其实本题就已经基本解决了，考虑到排序好的数组里的每一个数字，只有当它在最左端/最右端的时候才会对最后的结果产生贡献，我们只需要去计算每个数字出现的最左端和最右端的次数即可。而这个其实就是根据idx的一次全排列。
这里还有个需要注意的地方就是最后的数字会很大，所以题目中要求要对1e9 + 7取余数，在做取余操作的时候，我们不能够直接res += （***）% mod，必须使用 res = （res + ***） % mod，另外在最后的结果上为了避免出现负数的情况，需要再加上mod进行取余来规避掉负数的情况。
public int sumSubseqWidths(int[] A) {
long res = 0;
int n = A.length;
int mod = (int)1e9 + 7;
long[] dp = new long[n];
dp[0] = 1;
for (int i = 1; i < n; i++) {
dp[i] = (dp[i - 1] << 1) % mod;
}
Arrays.sort(A);
for (int i = 0; i < n; i++) {
// 不能使用 res += ***
res = (res + A[i] * dp[i] - A[i] * dp[n - i - 1]) % mod;
}
return (int)((res + mod) % mod);
}