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

Longest Subsequence With Decreasing Adjacent Difference

Number: 3716

Difficulty: Medium

Paid? No

Companies: Google

Problem Description

Given an array of integers nums, find the length of the longest subsequence seq such that the absolute differences between consecutive elements form a non-increasing sequence. In other words, for a subsequence seq0, seq1, seq2, …, seq_m, the condition |seq1 – seq0| >= |seq2 – seq1| >= … >= |seq_m – seq_(m-1)| must hold.

Key Insights

  • This is a dynamic programming problem where you need to keep track not only of the subsequence length but also the last difference between consecutive elements.
  • Using a DP state such as dp[i][d] to represent the length of the longest valid subsequence ending at index i with the last adjacent difference equal to d.
  • When extending a valid subsequence ending at index i to include a new element at index j, compute the new difference. It must be no larger than the previous difference for the subsequence to remain valid.
  • Since the values in nums are bounded (nums[i] <= 300), the possible differences are also limited, which helps in managing the state space.

Space and Time Complexity

Time Complexity: O(n^2 * D) in the worst case, where n is the number of elements in nums and D is the range of possible differences (which is small since nums[i] <= 300).
Space Complexity: O(n * D) for storing the DP state.

Solution

We use dynamic programming with a state dp[i][d] representing the maximum length of a valid subsequence ending at index i with its last adjacent difference equal to d. For every pair of indices (i, j) with i < j, we compute the absolute difference newDiff = |nums[j] – nums[i]|. Then, we consider all DP states from index i that have a previous difference (say currentDiff) such that newDiff <= currentDiff; this condition ensures that the sequence of differences stays non-increasing. We update dp[j][newDiff] accordingly. We also start a new valid pair (nums[i], nums[j]) by initializing dp[j][newDiff] to at least 2 if no previous state is extended. Finally, the answer is the maximum value found among all dp states.

Code Solutions

from collections import defaultdict

def longestSubsequence(nums):
    n = len(nums)
    # Create a list of dictionaries to maintain dp states:
    # dp[i][d] = length of longest subsequence ending at index i with last difference d.
    dp = [defaultdict(int) for _ in range(n)]
    res = 1  # At least every single number is a subsequence of length 1

    for j in range(n):
        for i in range(j):
            # Difference between nums[j] and nums[i]
            newDiff = abs(nums[j] - nums[i])
            # Try to extend each subsequence ending at index i
            best = 0
            for prevDiff in dp[i]:
                if newDiff <= prevDiff:
                    best = max(best, dp[i][prevDiff])
            # Minimum subsequence length is 2 (nums[i], nums[j])
            dp[j][newDiff] = max(dp[j][newDiff], best + 1, 2)
            res = max(res, dp[j][newDiff])
    return res

# Example usage:
print(longestSubsequence([16, 6, 3]))       # Output: 3
print(longestSubsequence([6,5,3,4,2,1]))     # Output: 4
print(longestSubsequence([10,20,10,19,10,20]))# Output: 5
← Back to All Questions