Longest Subsequence With Decreasing Adjacent Difference

Naive Approach

A brute force solution would involve generating all possible subsequences of the given array nums, and then checking if each subsequence satisfies the non-increasing absolute difference condition. We would keep track of the longest valid subsequence found so far.

Algorithm

1. Generate all subsequences of nums.
2. For each subsequence, calculate the absolute differences between consecutive elements.
3. Check if the absolute differences form a non-increasing sequence.
4. If it is, compare its length with the current maximum length and update if necessary.

Code (Python)

def is_non_increasing(arr):
    for i in range(len(arr) - 1):
        if arr[i] < arr[i+1]:
            return False
    return True

def longest_non_increasing_subsequence_brute_force(nums):
    max_len = 0
    for i in range(1 << len(nums)):
        subsequence = []
        for j in range(len(nums)):
            if (i >> j) & 1:
                subsequence.append(nums[j])
        
        if len(subsequence) < 2:
            max_len = max(max_len, len(subsequence))
            continue
            
        diffs = []
        for k in range(len(subsequence) - 1):
            diffs.append(abs(subsequence[k+1] - subsequence[k]))
        
        if is_non_increasing(diffs):
            max_len = max(max_len, len(subsequence))
            
    return max_len

# Example usage:
nums = [6, 5, 3, 4, 2, 1]
print(longest_non_increasing_subsequence_brute_force(nums))

Time Complexity

• Generating all subsequences takes O(2ⁿ) time, where n is the length of nums.
• For each subsequence, calculating absolute differences and checking the non-increasing property takes O(n) time in the worst case.
• Therefore, the overall time complexity is O(n * 2ⁿ).

Space Complexity

• O(n) to store the subsequence and the differences.

Optimal Approach: Dynamic Programming

A more efficient solution can be achieved using dynamic programming. We can build a DP table where dp[i] stores the length of the longest non-increasing subsequence ending at index i.

Algorithm

1. Initialize dp[i] = 1 for all i, as a single element is a subsequence of length 1.
2. Iterate through the array nums from i = 1 to n - 1.
3. For each i, iterate from j = 0 to i - 1.
4. If abs(nums[i] - nums[j]) is less than or equal to the minimum absolute difference seen so far for the subsequence ending at j (or if it's the first element), update dp[i] = max(dp[i], dp[j] + 1).
5. Keep track of the overall maximum length.

Code (Python)

def longest_non_increasing_subsequence_dp(nums):
    n = len(nums)
    dp = [1] * n
    max_len = 1

    for i in range(1, n):
        for j in range(i):
            if len(nums) > 0:
              diffs = []
              temp_list = [nums[j], nums[i]]
              for k in range(len(temp_list) - 1):
                  diffs.append(abs(temp_list[k+1] - temp_list[k]))

              candidate_list = nums[:j+1]
              candidate_subsequence = [nums[index] for index in range(len(nums)) if nums[index] in candidate_list]
              candidate_diffs = []
              if len(candidate_subsequence) > 1:
                for index_candidate in range(len(candidate_subsequence) - 1):
                  candidate_diffs.append(abs(candidate_subsequence[index_candidate+1] - candidate_subsequence[index_candidate]))

              if len(candidate_diffs) == 0 or diffs[0] <= min(candidate_diffs):  
                dp[i] = max(dp[i], dp[j] + 1)
                max_len = max(max_len, dp[i])

    return max_len

# Example usage:
nums = [6, 5, 3, 4, 2, 1]
print(longest_non_increasing_subsequence_dp(nums))

nums = [10,20,10,19,10,20]
print(longest_non_increasing_subsequence_dp(nums))

Time Complexity

The nested loops result in a time complexity of O(n²), where n is the length of nums.

Space Complexity

• O(n) for the dp table.

Edge Cases

• Empty array: Return 0.
• Array with one element: Return 1.
• Array with two elements: Check if the condition is met, return 2 if it is, and 1 otherwise.