Longest Subsequence With Decreasing Adjacent Difference

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. In other words, for a subsequence seq0, seq1, seq2, ..., seqm of nums, |seq1 - seq0| >= |seq2 - seq1| >= ... >= |seqm - seqm - 1|.

Return the length of such a subsequence.

Example 1:

Input: nums = [16,6,3] Output: 3 Explanation: The longest subsequence is [16, 6, 3] with the absolute adjacent differences [10, 3].

Example 2:

Input: nums = [6,5,3,4,2,1] Output: 4 Explanation: The longest subsequence is [6, 4, 2, 1] with the absolute adjacent differences [2, 2, 1].

Example 3:

Input: nums = [10,20,10,19,10,20] Output: 5 Explanation: The longest subsequence is [10, 20, 10, 19, 10] with the absolute adjacent differences [10, 10, 9, 9].

## Optimal Solution: Dynamic Programming

We can solve this problem using dynamic programming. Let `dp[i][j]` be the length of the longest subsequence ending at index `i` with the last absolute difference being `j`. We can iterate through the `nums` array and update the `dp` array based on the following logic:

1.  Initialize `dp[i][0] = 1` for all `i` because a single element is a subsequence of length 1.
2.  For each `i` from 1 to `n-1`:
    *   For each `j` from 0 to `i-1`:
        *   Calculate the absolute difference `diff = abs(nums[i] - nums[j])`.
        *   If `diff` is less than or equal to the last absolute difference in the subsequence ending at `j`, update `dp[i][diff] = max(dp[i][diff], dp[j][last_diff] + 1)`. We need to find the maximum `last_diff` from `dp[j]` where `last_diff >= diff`.

After filling the `dp` table, the maximum value in the `dp` table will be the length of the longest subsequence.

```python
def longest_subsequence(nums):
    n = len(nums)
    dp = {}
    for i in range(n):
        dp[i] = {}
        dp[i][0] = 1

    max_len = 1

    for i in range(1, n):
        for j in range(i):
            diff = abs(nums[i] - nums[j])
            for last_diff in dp[j]:
                if last_diff >= diff:
                    if diff not in dp[i]:
                        dp[i][diff] = 0
                    dp[i][diff] = max(dp[i][diff], dp[j][last_diff] + 1)
                    max_len = max(max_len, dp[i][diff])

    return max_len

# Example usage
nums1 = [16, 6, 3]
print(f"Longest subsequence for {nums1}: {longest_subsequence(nums1)}")  # Output: 3

nums2 = [6, 5, 3, 4, 2, 1]
print(f"Longest subsequence for {nums2}: {longest_subsequence(nums2)}")  # Output: 4

nums3 = [10, 20, 10, 19, 10, 20]
print(f"Longest subsequence for {nums3}: {longest_subsequence(nums3)}")  # Output: 5

Time Complexity Analysis

The time complexity is O(n² * m), where n is the length of the input array nums, and m is the maximum absolute difference between any two numbers in nums. In our case, m can be considered as a constant (300 due to constraints), but we should consider that dp[i] can store values up to 300. The nested loops iterate through all possible pairs of elements in nums, which takes O(n²) time. The inner loop iterates through all possible last differences which take O(m) where m is capped at 300. Therefore, the overall time complexity is O(n² * m).

Space Complexity Analysis

The space complexity is O(n * m), where n is the length of the input array nums and m is the range of absolute differences. The dp table stores the length of the longest subsequence ending at each index i with the last absolute difference being j. Therefore, the space complexity is O(n * m), where m is up to 300.

Edge Cases and Considerations

1. Empty Input: If the input array nums is empty, the function should return 0.
2. Single Element: If the input array nums has only one element, the function should return 1.
3. Duplicate Numbers: The presence of duplicate numbers in the input array should not affect the correctness of the algorithm.
4. All Elements Identical: If all elements in the input array are identical, the longest subsequence will be the entire array, and the function should return the length of the array. The absolute differences will all be 0 and the non-increasing condition holds.