We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Sum of Consecutive Subsequences

Number: 3623

Difficulty: Hard

Paid? Yes

Companies: N/A

Problem Description

Given an array of integers nums, we call a subsequence (not necessarily contiguous, but with preserved order) “consecutive” if the difference between every two adjacent elements is either always +1 or always –1. (Note that a single-element array is considered consecutive.) The value of an array is defined as the sum of its elements. Your goal is to return the sum of the values of all consecutive non-empty subsequences of nums modulo 10^9 + 7.

For example, for nums = [1,2] the valid consecutive subsequences are [1], [2], and [1,2] with total value 1 + 2 + (1+2) = 6. For nums = [1,4,2,3] the valid subsequences are [1], [4], [2], [3], [1,2], [2,3], [4,3] and [1,2,3] which sum to 31.

Key Insights

  • A valid subsequence (respecting original order) is one where adjacent elements differ by exactly +1 (increasing) or –1 (decreasing).
  • Every individual element (singleton) is trivially consecutive.
  • Directly enumerating subsequences is infeasible because there can be exponentially many; hence we use dynamic programming.
  • We can maintain two DP states—one for subsequences following an increasing pattern and one for those following a decreasing pattern.
  • When processing an element, it can start a new subsequence or extend a previously built subsequence if the required previous value exists.
  • For extension, if we already have some subsequences ending with (current - 1) for increasing (or (current + 1) for decreasing), then we create new subsequences by appending the current element. Their contribution to the "subsequence value" equals the previous total sum plus the current element multiplied by the count of sequences extended.
  • Since single-element subsequences appear in both cases (increasing and decreasing) and must be counted only once, we subtract one copy of the new element’s value when combining the two states.

Space and Time Complexity

Time Complexity: O(n) – We process each element once while updating and looking up in hash maps. Space Complexity: O(m) – Where m is the number of distinct nums values encountered (at most 10^5).

Solution

We iterate over nums in order. For each element x, we compute two “DP” values:

  1. For increasing subsequences (difference +1): Start a new subsequence with x, and if there are subsequences ending with x–1 already (stored in a dictionary dp_inc), extend each of them to now end with x. For an extension, if there are c subsequences ending with x–1 summing to S, the new contribution when extended with x is S + c*x.
  2. For decreasing subsequences (difference –1): Similarly, start a new subsequence and extend any subsequences ending with x+1 from a dictionary dp_dec.
  3. Since a singleton [x] is created in both increasing and decreasing cases, we subtract x once to avoid double counting.
  4. We add the contribution (sum) from new subsequences (increasing + decreasing, adjusted) to our final result and update dp_inc[x] and dp_dec[x] for use in subsequent extensions.

Each dp dictionary stores a pair:

  • count: number of valid subsequences ending with a certain value.
  • sum: total of sums (value sums) of these subsequences.

We use modulo arithmetic at every step to avoid overflow.

Code Solutions

# Python solution with line-by-line comments

MOD = 10**9 + 7

def sum_of_consecutive_subsequences(nums):
    # dp_inc and dp_dec are dictionaries mapping a value to a pair: (count, total_sum)
    dp_inc = {}  # For increasing sequences ending at a specific number
    dp_dec = {}  # For decreasing sequences ending at a specific number
    result = 0
    
    for x in nums:
        # Initialize the new subsequence starting at x (singleton).
        new_inc_count = 1
        new_inc_sum = x  % MOD
        new_dec_count = 1
        new_dec_sum = x  % MOD
        
        # For increasing sequences: if there are sequences ending with x - 1, extend them.
        if x - 1 in dp_inc:
            prev_count, prev_sum = dp_inc[x - 1]
            # Extend each subsequence ending with (x-1) by adding current x.
            new_inc_count = (new_inc_count + prev_count) % MOD
            new_inc_sum = (new_inc_sum + prev_sum + (prev_count * x) % MOD) % MOD
        
        # For decreasing sequences: if there are sequences ending with x + 1, extend them.
        if x + 1 in dp_dec:
            prev_count, prev_sum = dp_dec[x + 1]
            new_dec_count = (new_dec_count + prev_count) % MOD
            new_dec_sum = (new_dec_sum + prev_sum + (prev_count * x) % MOD) % MOD
        
        # Update dp_inc for x by accumulating new states.
        if x in dp_inc:
            count_old, sum_old = dp_inc[x]
            dp_inc[x] = ((count_old + new_inc_count) % MOD, (sum_old + new_inc_sum) % MOD)
        else:
            dp_inc[x] = (new_inc_count, new_inc_sum)
            
        # Update dp_dec for x similarly.
        if x in dp_dec:
            count_old, sum_old = dp_dec[x]
            dp_dec[x] = ((count_old + new_dec_count) % MOD, (sum_old + new_dec_sum) % MOD)
        else:
            dp_dec[x] = (new_dec_count, new_dec_sum)
        
        # Each new singleton [x] appears in both new_inc and new_dec.
        # To avoid double counting it, subtract one copy of x.
        combined_sum = (new_inc_sum + new_dec_sum - x) % MOD
        result = (result + combined_sum) % MOD
        
    return result

# Example usage:
#print(sum_of_consecutive_subsequences([1,2]))  # Expected output 6
#print(sum_of_consecutive_subsequences([1,4,2,3]))  # Expected output 31
← Back to All Questions