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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Longest Subsequence With Decreasing Adjacent Difference

Difficulty: Medium

Problem Description

You are given an array of integers nums. Your task is to find the length of the longest subsequence seq of nums, such that the absolute differences between consecutive elements form a non-increasing sequence of integers.

Return the length of such a subsequence.

Key Insights

  • The absolute differences between consecutive elements must be non-increasing.
  • We can utilize dynamic programming to track the maximum length of subsequences that satisfy the condition.
  • The problem can be approached by storing the differences and ensuring they follow the non-increasing order as we iterate through the array.

Space and Time Complexity

Time Complexity: O(n^2)
Space Complexity: O(n)

Solution

The solution employs a dynamic programming approach where we maintain an array dp that stores the maximum length of the subsequence ending at each index. We iterate through the array, and for each element, we check all previous elements to find valid subsequences. If the absolute difference condition is met, we update our dp array accordingly. Finally, the maximum value in the dp array gives the length of the longest valid subsequence.

Code Solutions

def longest_subsequence(nums):
    n = len(nums)
    dp = [1] * n  # Initialize dp array where each element can be a subsequence of length 1

    for i in range(n):
        for j in range(i):
            diff1 = abs(nums[i] - nums[j])
            if dp[j] > 1:  # Only consider previous subsequences of length > 1
                for k in range(j):
                    diff2 = abs(nums[j] - nums[k])
                    if diff1 <= diff2:  # Check for non-increasing condition
                        dp[i] = max(dp[i], dp[j] + 1)

    return max(dp)  # The maximum length of the valid subsequence
← Back to All Questions