Skip to content

3351. Sum of Good Subsequences

SourceWeekly Contest 423 Q3DifficultyHardRating2085

Description

You are given an integer array nums. A good subsequence is defined as a subsequence of nums where the absolute difference between any two consecutive elements in the subsequence is exactly 1.

Return the sum of all possible good subsequences of nums.

Since the answer may be very large, return it modulo 109 + 7.

Note that a subsequence of size 1 is considered good by definition.

 

Example 1:

Input: nums = [1,2,1]

Output: 14

Explanation:

  • Good subsequences are: [1], [2], [1], [1,2], [2,1], [1,2,1].
  • The sum of elements in these subsequences is 14.

Example 2:

Input: nums = [3,4,5]

Output: 40

Explanation:

  • Good subsequences are: [3], [4], [5], [3,4], [4,5], [3,4,5].
  • The sum of elements in these subsequences is 40.

 

Constraints:

  • 1 <= nums.length <= 105
  • 0 <= nums[i] <= 105

Solutions

Solution 1

Thinking

A good subsequence has consecutive absolute differences equal to \(1\). With \(n \le 10^5\) we cannot list subsequences; we DP on values.

Let \(g[x]\) be the number of good subsequences ending with \(x\) and \(f[x]\) their element sum. A new \(x\) starts a singleton or appends to existing \(x-1\) or \(x+1\).

Appending adds “old sum + old count \(\times x\)”. Updates follow input order so earlier copies of \(x\) are included. The answer is the sum of all \(f\), modulo \(10^9+7\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
    def sumOfGoodSubsequences(self, nums: List[int]) -> int:
        mod = 10**9 + 7
        f = defaultdict(int)
        g = defaultdict(int)
        for x in nums:
            f[x] += x
            g[x] += 1
            f[x] += f[x - 1] + g[x - 1] * x
            g[x] += g[x - 1]
            f[x] += f[x + 1] + g[x + 1] * x
            g[x] += g[x + 1]
        return sum(f.values()) % mod

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
    public int sumOfGoodSubsequences(int[] nums) {
        final int mod = (int) 1e9 + 7;
        int mx = 0;
        for (int x : nums) {
            mx = Math.max(mx, x);
        }
        long[] f = new long[mx + 1];
        long[] g = new long[mx + 1];
        for (int x : nums) {
            f[x] += x;
            g[x] += 1;
            if (x > 0) {
                f[x] = (f[x] + f[x - 1] + g[x - 1] * x % mod) % mod;
                g[x] = (g[x] + g[x - 1]) % mod;
            }
            if (x + 1 <= mx) {
                f[x] = (f[x] + f[x + 1] + g[x + 1] * x % mod) % mod;
                g[x] = (g[x] + g[x + 1]) % mod;
            }
        }
        long ans = 0;
        for (long x : f) {
            ans = (ans + x) % mod;
        }
        return (int) ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    int sumOfGoodSubsequences(vector<int>& nums) {
        const int mod = 1e9 + 7;
        int mx = ranges::max(nums);

        vector<long long> f(mx + 1), g(mx + 1);
        for (int x : nums) {
            f[x] += x;
            g[x] += 1;

            if (x > 0) {
                f[x] = (f[x] + f[x - 1] + g[x - 1] * x % mod) % mod;
                g[x] = (g[x] + g[x - 1]) % mod;
            }

            if (x + 1 <= mx) {
                f[x] = (f[x] + f[x + 1] + g[x + 1] * x % mod) % mod;
                g[x] = (g[x] + g[x + 1]) % mod;
            }
        }

        return accumulate(f.begin(), f.end(), 0LL) % mod;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
func sumOfGoodSubsequences(nums []int) (ans int) {
    mod := int(1e9 + 7)
    mx := slices.Max(nums)

    f := make([]int, mx+1)
    g := make([]int, mx+1)

    for _, x := range nums {
        f[x] += x
        g[x] += 1

        if x > 0 {
            f[x] = (f[x] + f[x-1] + g[x-1]*x%mod) % mod
            g[x] = (g[x] + g[x-1]) % mod
        }

        if x+1 <= mx {
            f[x] = (f[x] + f[x+1] + g[x+1]*x%mod) % mod
            g[x] = (g[x] + g[x+1]) % mod
        }
    }

    for _, x := range f {
        ans = (ans + x) % mod
    }
    return
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
function sumOfGoodSubsequences(nums: number[]): number {
    const mod = 10 ** 9 + 7;
    const mx = Math.max(...nums);
    const f: number[] = Array(mx + 1).fill(0);
    const g: number[] = Array(mx + 1).fill(0);
    for (const x of nums) {
        f[x] += x;
        g[x] += 1;
        if (x > 0) {
            f[x] = (f[x] + f[x - 1] + ((g[x - 1] * x) % mod)) % mod;
            g[x] = (g[x] + g[x - 1]) % mod;
        }
        if (x + 1 <= mx) {
            f[x] = (f[x] + f[x + 1] + ((g[x + 1] * x) % mod)) % mod;
            g[x] = (g[x] + g[x + 1]) % mod;
        }
    }
    return f.reduce((acc, cur) => (acc + cur) % mod, 0);
}

Comments