Longest Subsequence With Decreasing Adjacent Difference

1. Define a 2D DP table dp[v][d], where dp[v][d] stores the length of the longest valid subsequence ending with the value v and having a last absolute difference of d.
2. Define an auxiliary array maxLen[v] to store the maximum length of any valid subsequence ending with value v. This helps to quickly check if a value has been encountered before.
3. Initialize dp and maxLen tables with 0. The answer ans is initialized to 1 (for single-element subsequences).
4. Iterate through each number num in the input array nums.
5. For each num, iterate through all possible previous values prev_v from 1 to 300.
6. If maxLen[prev_v] > 0, it means prev_v has been seen. We can potentially extend a subsequence ending at prev_v with num.
7. Calculate the new difference d = |num - prev_v|.
8. To satisfy the non-increasing difference condition, the previous difference prev_d must be greater than or equal to d. We find the maximum length of a subsequence ending at prev_v that meets this condition by iterating from d to the maximum possible difference. len_to_extend = max(dp[prev_v][k]) for k >= d.
9. The new subsequence length will be len_to_extend + 1. If no such subsequence exists (len_to_extend == 0), we can still form a new subsequence of length 2, [prev_v, num].
10. Update a temporary DP row for num with the calculated new length.
11. After checking all possible prev_v, merge the temporary row into the main dp[num] row and update maxLen[num] and the overall ans.

The core of this method is a 2D DP table, dp[v][d], which stores the length of the longest valid subsequence ending with value v and a final difference of d. We also use an auxiliary array, maxLen[v], to keep track of the maximum length of any subsequence ending in v, which helps us know if v has appeared in nums so far.

We process the input array nums one element at a time. For each num, we try to form a new, longer subsequence by appending num to existing valid subsequences. We iterate through all possible previous values prev_v (from 1 to 300). If prev_v has been seen before (i.e., maxLen[prev_v] > 0), we calculate the new difference d = |num - prev_v|. We then perform a search within dp[prev_v] to find the longest subsequence we can extend, which is one whose last difference prev_d is at least d. This search is a linear scan, contributing to the high time complexity. After calculating the potential new lengths for all prev_v, we update the DP table for num.

1class Solution {2    public int longestSubsequence(int[] nums) {3        int V_MAX = 300;4        int D_MAX = 300;5 6        // dp[v][d]: length of the longest valid subsequence ending with value v and last difference d7        int[][] dp = new int[V_MAX + 1][D_MAX];8        // maxLen[v]: max length of any valid subsequence ending with value v9        int[] maxLen = new int[V_MAX + 1];10        11        int ans = 1;12 13        for (int num : nums) {14            int[] newDpRowForNum = new int[D_MAX];15            int newMaxLenForNum = 1;16 17            for (int prev_v = 1; prev_v <= V_MAX; prev_v++) {18                if (maxLen[prev_v] > 0) { // if prev_v has been seen before19                    int d = Math.abs(num - prev_v);20                    21                    // Find max length of subsequence ending at prev_v with last diff >= d22                    int lenToExtend = 0;23                    for (int prev_d = d; prev_d < D_MAX; prev_d++) {24                        lenToExtend = Math.max(lenToExtend, dp[prev_v][prev_d]);25                    }26                    27                    int newLen = (lenToExtend == 0) ? 2 : lenToExtend + 1;28                    29                    newDpRowForNum[d] = Math.max(newDpRowForNum[d], newLen);30                    newMaxLenForNum = Math.max(newMaxLenForNum, newLen);31                }32            }33 34            for (int d = 0; d < D_MAX; d++) {35                dp[num][d] = Math.max(dp[num][d], newDpRowForNum[d]);36            }37            38            maxLen[num] = Math.max(maxLen[num], newMaxLenForNum);39            if (maxLen[num] == 0) {40                maxLen[num] = 1;41            }42            43            ans = Math.max(ans, maxLen[num]);44        }45 46        return ans;47    }48}

1. Use the same DP state dp[v][d] and maxLen[v] as the previous approach.
2. Introduce a new auxiliary table, suffixMaxDp[v][d], which stores the suffix maximum of each row in the dp table. Specifically, suffixMaxDp[v][d] = max(dp[v][k]) for all k >= d.
3. Initialize all tables to 0 and ans to 1.
4. Iterate through each num in nums.
5. For each num, iterate through all possible previous values prev_v.
6. If prev_v has been seen (maxLen[prev_v] > 0), calculate the new difference d = |num - prev_v|.
7. The crucial optimization: instead of looping to find the best previous subsequence to extend, we can get this information in O(1) time from our precomputed suffix maximum table: len_to_extend = suffixMaxDp[prev_v][d].
8. Calculate the new length (2 if len_to_extend is 0, otherwise len_to_extend + 1) and update a temporary DP row for num.
9. After checking all prev_v, update the main dp[num] table.
10. If dp[num] was modified, the corresponding suffixMaxDp[num] row must be recomputed. This takes O(D_max) time.
11. Update maxLen[num] and the overall ans.

We build upon the previous DP approach. The state dp[v][d] and helper array maxLen[v] remain the same. The key addition is the suffixMaxDp[v][d] table, which is maintained throughout the process. For each num in the input array, we calculate the potential new lengths of subsequences ending in num.

For each possible previous value prev_v, we determine the new difference d = |num - prev_v|. Instead of a loop, we directly query suffixMaxDp[prev_v][d] to find the length of the longest subsequence ending in prev_v with a last difference of at least d. This is an O(1) lookup. Based on this, we calculate the new length and store it temporarily.

After considering all possible prev_v, we update the dp[num] row with the new values. A crucial step follows: if the dp[num] row has changed, we must re-calculate the suffixMaxDp[num] row to ensure it's correct for subsequent iterations. This update takes O(D_max) time. This optimization brings the total time complexity down to a feasible level.

1class Solution {2    public int longestSubsequence(int[] nums) {3        int V_MAX = 300;4        int D_MAX = 300;5 6        int[][] dp = new int[V_MAX + 1][D_MAX];7        int[] maxLen = new int[V_MAX + 1];8        int[][] suffixMaxDp = new int[V_MAX + 1][D_MAX];9 10        int ans = 1;11 12        for (int num : nums) {13            int[] newDpRowForNum = new int[D_MAX];14            int newMaxLenForNum = 1;15 16            for (int prev_v = 1; prev_v <= V_MAX; prev_v++) {17                if (maxLen[prev_v] > 0) {18                    int d = Math.abs(num - prev_v);19                    int lenToExtend = suffixMaxDp[prev_v][d];20                    int newLen = (lenToExtend == 0) ? 2 : lenToExtend + 1;21                    newDpRowForNum[d] = Math.max(newDpRowForNum[d], newLen);22                    newMaxLenForNum = Math.max(newMaxLenForNum, newLen);23                }24            }25 26            boolean updated = false;27            for (int d = 0; d < D_MAX; d++) {28                if (newDpRowForNum[d] > dp[num][d]) {29                    dp[num][d] = newDpRowForNum[d];30                    updated = true;31                }32            }33            34            maxLen[num] = Math.max(maxLen[num], newMaxLenForNum);35            if (maxLen[num] == 0) maxLen[num] = 1;36 37            if (updated) {38                int suffixMax = 0;39                for (int d = D_MAX - 1; d >= 0; d--) {40                    suffixMax = Math.max(suffixMax, dp[num][d]);41                    suffixMaxDp[num][d] = suffixMax;42                }43            }44            45            ans = Math.max(ans, maxLen[num]);46        }47 48        return ans;49    }50}