🔥 Easy Explanation Longest Arithmetic Subsequence – DP with Suffix Max Optimization 🚀
Intuition
The problem requires finding the longest subsequence where the absolute difference between consecutive elements remains the same.
Instead of checking
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
- The problem requires finding the longest subsequence where the absolute difference between consecutive elements remains the same.
- Instead of checking all possible subsequences, we can dynamically compute the longest valid subsequence ending at each number using Dynamic Programming (DP).
- We maintain a DP table where:
dp[num][d] stores the length of the longest subsequence ending at num with a difference of d.
- suffixMax[num][d] helps track the best sequence ending at num efficiently.

# Approach
<!-- Describe your approach to solving the problem. -->
Initialize DP and Suffix Max Arrays

- dp[num][d]: Stores the longest subsequence ending at num with common difference d.
- suffixMax[num][d]: Keeps track of the maximum dp[num][d] for all d >= current d (used for efficient lookup).
Iterate Through the Numbers

- If num is encountered for the first time, set dp[num][0] = 1 (starting new sequence).
- For each possible prevNum, compute dNew = |num - prevNum| and update dp[num][dNew] using:
The best existing subsequence with dNew difference.
If no such sequence exists, start a new subsequence of length 2.
Update suffixMax

- This helps retrieve the best subsequence ending at num for a given dNew.
Return the Maximum Subsequence Length



# Complexity
- Time complexity:
<!-- Add your time complexity here, e.g. $$O(n)$$ -->
O(n×300)=O(n)

- Space complexity:
<!-- Add your space complexity here, e.g. $$O(n)$$ -->
DP Table (dp[301][301]): O(300 × 300) = O(90,000) ≈ O(1), since it's a fixed-size 2D array.
Suffix Max Table (suffixMax[301][301]): Same as DP table.

# Code
```java []
class Solution {
    // DP table where dp[num][d] stores the longest subsequence ending at 'num' with common difference 'd'
    int[][] dp = new int[301][301];

    // Suffix max table to store the maximum dp[num][d] for all d >= current d (used for fast lookup)
    int[][] suffixMax = new int[301][301];

    public int longestSubsequence(int[] nums) {
        int ans = 1; // Stores the maximum length of valid subsequence

        // Iterate through each number in the input array
        for (int num : nums) {
            // If 'num' appears for the first time, start a new subsequence
            if (dp[num][0] < 1) {
                dp[num][0] = 1; // Initialize to 1
            }

            // Iterate over all possible previous numbers in the range [1, 300]
            for (int prevNum = 1; prevNum <= 300; prevNum++) {
                // Calculate the absolute difference between 'num' and 'prevNum'
                int dNew = Math.abs(num - prevNum);

                // Find the longest subsequence ending at 'prevNum' with difference 'dNew'
                int bestChain = suffixMax[prevNum][dNew];

                // If there exists a valid subsequence with difference 'dNew', extend it
                if (bestChain > 1) {
                    dp[num][dNew] = Math.max(dp[num][dNew], bestChain + 1);
                } 
                // Otherwise, start a new sequence of length 2 if 'prevNum' exists
                else {
                    if (suffixMax[prevNum][0] > 0) {
                        dp[num][dNew] = Math.max(dp[num][dNew], 2);
                    }
                }

                // Update the global maximum answer
                ans = Math.max(ans, dp[num][dNew]);
            }

            // Update the suffix max array for 'num'
            suffixMax[num][299] = dp[num][299];

            // Compute the suffix max for all possible differences
            for (int d = 298; d >= 0; d--) {
                suffixMax[num][d] = Math.max(suffixMax[num][d + 1], dp[num][d]);
            }
        }
        return ans; // Return the maximum length of a valid subsequence found
    }
}

```
['Array', 'Dynamic Programming', 'Java']