🔥 O(N) DP Solution for Longest Subsequence! 🚀
IntuitionThe problem requires finding the longest subsequence in an array of integers where the absolute difference between adjacent elements is decreasing. Thi
### Intuition  

The problem requires finding the **longest subsequence** in an array of integers where the **absolute difference between adjacent elements is decreasing**. This can be solved efficiently using **dynamic programming** (DP) combined with tracking values and their differences.

---

### Approach  

1. **Understanding the Problem:**  
   - For each number in the sequence, consider the absolute differences with previously seen numbers.
   - Maintain a DP table that stores the longest subsequence length for each number with a specific difference.  

2. **Dynamic Programming Setup:**  
   - Use a 2D DP array `dp[num][diff]`:
     - `dp[num][diff]` represents the longest subsequence ending at `num` with an adjacent difference of `diff`.
   - Additionally, maintain an array `arr` to track whether a number has been processed.  

3. **Iterating Through the Array:**  
   - For each number, calculate the possible subsequences that can be extended:
     - Iterate through all possible previous numbers.
     - Compute the absolute difference between the current and previous numbers.  
   - Update the DP values for all decreasing differences.  

4. **Optimizing DP Transitions:**  
   - To ensure correctness and efficiency:
     - Iterate over all possible differences and update the DP table.
     - Use a maximum-tracking mechanism to avoid redundant calculations.  

5. **Result Extraction:**  
   - The result is the maximum value in the DP table, representing the length of the longest valid subsequence.

---

### Complexity  

- **Time Complexity:**  
  - **Outer loop:** $$O(n)$$ to process each number.  
  - **Inner loop:** $$O(300)$$ for iterating over the difference table.  
  - Overall: $$O(n \times 300)$$.  

- **Space Complexity:**  
  - $$O(300 \times 300)$$ for the DP table.  
  - $$O(300)$$ for the `arr` array.  

---

### Code  

```cpp []
class Solution {
public:
    int longestSubsequence(vector<int>& nums) {
        vector<int> arr(301, 0); // Track seen numbers
        vector<vector<int>> dp(301, vector<int>(301, 0)); // DP table
        int ans = 0;
        
        for (int num : nums) {
            // Check previous numbers for valid subsequences
            for (int i = 300; i >= 0; --i) {
                if (arr[i]) {
                    int diff = abs(num - i);
                    dp[num][diff] = max(dp[num][diff], dp[i][diff] + 1);
                }
            }
            
            // Ensure all smaller differences are handled
            for (int i = 299; i >= 0; --i) {
                dp[num][i] = max(dp[num][i], dp[num][i + 1]);
            }
            
            // Track the global maximum
            ans = max(ans, dp[num][0]);
            arr[num] = 1; // Mark current number as processed
        }
        
        return ans + 1; // Add 1 to account for the current number
    }
};
```
``` python3 []
class Solution:
    def longestSubsequence(self, nums: List[int]) -> int:
        dp = [[0] * 301 for _ in range(301)]  # DP table
        arr = [0] * 301  # Tracks seen numbers
        ans = 0

        for num in nums:
            # Update dp for all valid differences
            for i in range(300, -1, -1):
                if arr[i]:
                    diff = abs(num - i)
                    dp[num][diff] = max(dp[num][diff], dp[i][diff] + 1)

            # Ensure smaller differences are consistent
            for i in range(299, -1, -1):
                dp[num][i] = max(dp[num][i], dp[num][i + 1])

            # Update the global maximum
            ans = max(ans, dp[num][0])
            arr[num] = 1  # Mark number as processed

        return ans + 1  # Add 1 for the current number
```

```golang []
func longestSubsequence(nums []int) int {
    dp := make([][]int, 301)
    for i := range dp {
        dp[i] = make([]int, 301)
    }
    arr := make([]bool, 301)
    ans := 0
    
    for _, num := range nums {
        for i := 300; i >= 0; i-- {
            if arr[i] {
                diff := abs(num - i)
                dp[num][diff] = max(dp[num][diff], dp[i][diff] + 1)
            }
        }
        for i := 299; i >= 0; i-- {
            dp[num][i] = max(dp[num][i], dp[num][i+1])
        }
        ans = max(ans, dp[num][0])
        arr[num] = true
    }
    return ans + 1
}

func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}
```

```rust []
impl Solution {
    pub fn longest_subsequence(nums: Vec<i32>) -> i32 {
        let mut dp = vec![vec![0; 301]; 301];
        let mut arr = vec![false; 301];
        let mut ans = 0;
        
        for &num in &nums {
            for i in (0..=300).rev() {
                if arr[i] {
                    let diff = (num - i as i32).abs() as usize;
                    dp[num as usize][diff] = dp[num as usize][diff].max(dp[i][diff] + 1);
                }
            }
            for i in (0..300).rev() {
                dp[num as usize][i] = dp[num as usize][i].max(dp[num as usize][i+1]);
            }
            ans = ans.max(dp[num as usize][0]);
            arr[num as usize] = true;
        }
        
        ans + 1
    }
}
```

```csharp []
public class Solution {
    public int LongestSubsequence(int[] nums) {
        int[,] dp = new int[301, 301];
        bool[] arr = new bool[301];
        int ans = 0;
        
        foreach (int num in nums) {
            for (int i = 300; i >= 0; --i) {
                if (arr[i]) {
                    int diff = Math.Abs(num - i);
                    dp[num, diff] = Math.Max(dp[num, diff], dp[i, diff] + 1);
                }
            }
            for (int i = 299; i >= 0; --i) {
                dp[num, i] = Math.Max(dp[num, i], dp[num, i + 1]);
            }
            ans = Math.Max(ans, dp[num, 0]);
            arr[num] = true;
        }
        
        return ans + 1;
    }
}
```  

---

### Examples  

#### Example 1:  
**Input:**  
`nums = [1, 5, 7, 9, 2, 6]`  
**Execution:**  
- Build subsequences like `[1, 5, 9]`, `[7, 9]`, or `[2, 6]` with decreasing adjacent differences.  

**Output:**  
`3`

#### Example 2:  
**Input:**  
`nums = [10, 12, 14, 8, 6, 4]`  
**Execution:**  
- Longest subsequence is `[10, 8, 6, 4]`.  

**Output:**  
`4`

---

### Edge Cases  

1. **All Numbers are Equal:**  
   - Input: `[5, 5, 5]`  
   - Output: `3` (All elements form a subsequence).

3. **Single Element:**  
   - Input: `[1]`  
   - Output: `1`  

['Array', 'Dynamic Programming', 'C++', 'Go', 'Python3', 'Rust', 'C#']