sum-of-subsequence-widths

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

The width of a sequence is the difference between the maximum and minimum elements in the sequence.

Given an array of integers <code>nums</code>, return the sum of the widths of all the non-empty subsequences of <code>nums</code>. Since the answer may be very large, return it modulo <code>109 + 7</code>.

A subsequence is a sequence that can be derived from an array by deleting some or no elements without changing the order of the remaining elements. For example, <code>[3,6,2,7]</code> is a subsequence of the array <code>[0,3,1,6,2,2,7]</code>.

&nbsp;
Example 1:

<pre>
Input: nums = [2,1,3]
Output: 6
Explanation: The subsequences are [1], [2], [3], [2,1], [2,3], [1,3], [2,1,3].
The corresponding widths are 0, 0, 0, 1, 1, 2, 2.
The sum of these widths is 6.
</pre>

Example 2:

<pre>
Input: nums = [2]
Output: 0
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= nums.length &lt;= 105</code></li>
	<li><code>1 &lt;= nums[i] &lt;= 105</code></li>
</ul>

sumSubseqWidths

Sum of Subsequence Widths

Array

Math

Sorting

一个序列的 宽度 定义为该序列中最大元素和最小元素的差值。

给你一个整数数组 <code>nums</code> ，返回 <code>nums</code> 的所有非空 子序列 的 宽度之和 。由于答案可能非常大，请返回对 <code>109 + 7</code> 取余 后的结果。

子序列 定义为从一个数组里删除一些（或者不删除）元素，但不改变剩下元素的顺序得到的数组。例如，<code>[3,6,2,7]</code> 就是数组 <code>[0,3,1,6,2,2,7]</code> 的一个子序列。

&nbsp;

示例 1：

<pre>
输入：nums = [2,1,3]
输出：6
解释：子序列为 [1], [2], [3], [2,1], [2,3], [1,3], [2,1,3] 。
相应的宽度是 0, 0, 0, 1, 1, 2, 2 。
宽度之和是 6 。
</pre>

示例 2：

<pre>
输入：nums = [2]
输出：0
</pre>

&nbsp;

提示：

<ul>
	<li><code>1 &lt;= nums.length &lt;= 105</code></li>
	<li><code>1 &lt;= nums[i] &lt;= 105</code></li>
</ul>