3646. Sum of Good Subsequences
My accepted Python solution to LeetCode problem 3646, Sum of Good Subsequences, running in 441ms.
- Difficulty: Hard
- Python
- Runtime 441ms
- Memory 32MB
- Updated
Read the problem on LeetCode View on GitHub
The problem statement is LeetCode’s and stays on their site. What follows is my accepted solution.
Python
Accepted on LeetCode — runtime 441ms, memory 32MB, accepted 2025-12-31.
class Solution:
def sumOfGoodSubsequences(self, nums: List[int]) -> int:
MOD = 10**9 + 7
# For each value v, track:
# - count[v]: number of good subsequences ending with v
# - total[v]: sum of all elements in good subsequences ending with v
from collections import defaultdict
count = defaultdict(int)
total = defaultdict(int)
result = 0
for x in nums:
# New subsequences ending at x can come from:
# 1. Just x itself
# 2. Extending subsequences ending at x-1
# 3. Extending subsequences ending at x+1
new_count = 1 # Just x itself
new_total = x # Just x itself
# From x-1
if x - 1 in count:
new_count = (new_count + count[x-1]) % MOD
# Each subsequence ending at x-1 adds its total + x * count
new_total = (new_total + total[x-1] + x * count[x-1]) % MOD
# From x+1
if x + 1 in count:
new_count = (new_count + count[x+1]) % MOD
new_total = (new_total + total[x+1] + x * count[x+1]) % MOD
count[x] = (count[x] + new_count) % MOD
total[x] = (total[x] + new_total) % MOD
result = (result + new_total) % MOD
return result