LCS (dp + binarysearch)
Intuition

ApproachTo solve this problem, we need a way to track and compare subsequences that meet the criteria. Here's the approach step-by-step:

Dynamic Pro
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
-
# Approach
To solve this problem, we need a way to track and compare subsequences that meet the criteria. Here's the approach step-by-step:

1. Dynamic Programming with a Twist: The problem can be solved using a dynamic programming approach. For each element in the sequence, we need to maintain a state for every possible absolute difference (denoted diff), which represents the absolute difference between the current element and the previous element in the subsequence. We will consider all such differences as we progress through the array.

1. Data Structures:
We will maintain a list a where a[i] holds the subsequences ending with value i in the array.
For each element nums[i], we'll generate possible subsequences by adding nums[i] to any subsequence that ends in a compatible element from the previous subsequences (those with diff >= 0).
Merging Subsequence Information: The main trick is to merge subsequences and update the longest subsequence lengths based on conditions on absolute differences. If an element can extend a subsequence where the absolute difference is larger than or equal to the current one, we extend it.

1. Efficient Look-up for Maximum Length:
We need to search for the longest subsequence where the difference is compatible, which can be efficiently achieved using binary search (as seen in the perform function). This helps us find the longest subsequence for each difference efficiently.
Final Result: Once we process all elements, the result will be the maximum length of any subsequence we've found.<!-- Describe your approach to solving the problem. -->

# Complexity
Time complexity:
- Let n be the length of the array.
- The outer loop runs for each element of the array (O(n)).
- For each element, we examine every possible difference (diff), which can be up to a maximum constant value MAX.
- For each difference, we perform a binary search to find the longest valid subsequence (O(log M) where M is the number of subsequences).
- Thus, the time complexity is approximately O(n * MAX * log M).
- Given that MAX is a constant (300), this complexity is manageable for typical input sizes.
<!-- Add your time complexity here, e.g. $$O(n)$$ -->

Space complexity:
<!-- Add your space complexity here, e.g. $$O(n)$$ -->

# Code
```java []
class Solution {
        public int longestSubsequence(int[] nums) {
            int n = nums.length;
            int MAX = 300;
            List<int[]>[] a = new List[MAX+1];
            for (int i = 1; i <= MAX; i++) {
                a[i] = new ArrayList<>();
            }
            for (int i = 0; i < n; i++) {
                List<int[]> c = new ArrayList<>();
                for (int j = 0; j <= MAX; j++) {
                    if(nums[i]+j<=MAX && nums[i]-j>=1) {
                        int x1 = perform(a[nums[i]+j], j);
                        int x2 = perform(a[nums[i]-j], j);
                        c.add(new int[]{j, Math.max(x1,x2) + 1});
                    } else if(nums[i]+j<=MAX) {
                        int x1 = perform(a[nums[i]+j], j);
                        c.add(new int[]{j, x1 + 1});
                    } else if(nums[i]-j>=1) {
                        int x1 = perform(a[nums[i]-j], j);
                        c.add(new int[]{j, x1 + 1});
                    } else {
                        break;
                    }
                }
                if(a[nums[i]].isEmpty()) {
                    c.add(new int[]{MAX, 1});
                }
                a[nums[i]] = merge(a[nums[i]], c);
//                for (int[] j:c) {
//                    System.out.println(j[0] + " " + j[1]);
//                }
//                for (int[] j:a[nums[i]]) {
//                    System.out.println(j[0] + " " + j[1]);
//                }
            }
            int ans = 0;
            for (int i = 1; i <= MAX; i++) {
                if(!a[i].isEmpty()) {
//                    if(a[i].size()>1) {
//                        System.out.println(i + " values : ");
//                        for (int[] j:a[i]) {
//                            System.out.print(j[0] + " " + j[1] + " , ");
//                        }
//                    }
                    ans = Math.max(ans, a[i].getLast()[1]);
                }
            }
            return ans;
        }

        public int perform(List<int[]> c, int maxDiff) {
            int s = 0;
            int e = c.size()-1;
            int ans = 0;
            while (s<=e) {
                int m = (s+e)/2;
                if(c.get(m)[0]<maxDiff) {
                    e = m - 1;
                } else {
                    ans = Math.max(ans, c.get(m)[1]);
                    s = m + 1;
                }
            }
            return ans;
        }

        public List<int[]> merge(List<int[]> a, List<int[]> b) {
            List<int[]> c = new ArrayList<>();
            int n = a.size();
            int m = b.size();
            int i = 0, j = m-1;
            while (i<=n-1 || j>=0) {
                if(i<=n-1 && j>=0) {
                    if(a.get(i)[0] == b.get(j)[0]) {
                        int x = Math.max(a.get(i)[1], b.get(j)[1]);
                        if(c.isEmpty() || x>c.getLast()[1]) {
                            c.add(new int[]{a.get(i)[0], x});
                        }
                        i++;
                        j--;
                    } else if(a.get(i)[0] > b.get(j)[0]) {
                        int x = a.get(i)[1];
                        if(c.isEmpty() || x>c.getLast()[1]) {
                            c.add(new int[]{a.get(i)[0], x});
                        }
                        i++;
                    } else if(a.get(i)[0] < b.get(j)[0]) {
                        int x = b.get(j)[1];
                        if(c.isEmpty() || x>c.getLast()[1]) {
                            c.add(new int[]{b.get(j)[0], x});
                        }
                        j--;
                    }
                } else if(i<=n-1) {
                    int x = a.get(i)[1];
                    if(c.isEmpty() || x>c.getLast()[1]) {
                        c.add(new int[]{a.get(i)[0], x});
                    }
                    i++;
                } else if(j>=0) {
                    int x = b.get(j)[1];
                    if(c.isEmpty() || x>c.getLast()[1]) {
                        c.add(new int[]{b.get(j)[0], x});
                    }
                    j--;
                } else break;
            }
            return c;
        }
    }

```
['Java']