Leetcode 927 Solution

This article provides solution to leetcode question 927 (sum-of-subsequence-widths)
Categories:
Tags:
Access this page by simply typing in "lcs 927" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/sum-of-subsequence-widths

Solution

class Solution:
    def sumSubseqWidths(self, A: List[int]) -> int:
        if len(A) == 1:
            return 0

        A.sort()

        ans = 0
        dp1 = 2
        dp2 = A[0]
        for i in range(1, len(A)):
            ans = (ans + A[i] * (dp1 - 1) - dp2) % (10**9 + 7)
            dp1 = (dp1 * 2) % (10**9 + 7)
            dp2 = (dp2 * 2 + A[i]) % (10**9 + 7)

        return ans