Sum of Subsequence Widths

Problem Description

Given an array of integers nums, return the sum of the widths of all the non-empty subsequences of nums. The width of a sequence is defined as the difference between the maximum and minimum elements in the sequence. Since the answer may be very large, return it modulo 10^9 + 7.

Key Insights

• A subsequence can be formed by deleting some or no elements from the array while maintaining the order.
• The contribution of each element to the total width depends on its position relative to other elements.
• Sort the array to easily find how many subsequences an element can be the maximum or minimum.
• Use combinatorial mathematics to calculate the contributions efficiently.

Space and Time Complexity

Time Complexity: O(n log n) - due to sorting the array.
Space Complexity: O(1) - only a constant amount of extra space used.

Solution

To solve the problem, the approach involves the following steps:

1. Sort the array: This allows us to easily determine the maximum and minimum elements of any subsequence.
2. Calculate contributions: For each element in the sorted array, calculate how many subsequences it can contribute to as a maximum and as a minimum.
   • For an element at index i, it can be the maximum in 2^i subsequences (all combinations of elements before it).
   • It can be the minimum in 2^(n - i - 1) subsequences (all combinations of elements after it).
3. Accumulate the total width: The contribution to the total width from each element is the difference between its value times the number of subsequences it can be a maximum and the number of subsequences it can be a minimum.

This approach efficiently computes the result without needing to explicitly enumerate all subsequences.

Code Solutions